Tap Dance

Changyoung and Hyunwoo attend a tap dance academy. In tap dance, dancers wear shoes with metal taps on the soles and strike the floor rhythmically. After discovering that they have a talent for dancing, they decide to create their own choreography.

A tap dance choreography is represented by a sequence of length N consisting of L and R. L means tapping the floor with the left foot, and R means tapping it with the right foot. Changyoung believes the choreography looks best when the same foot is not used twice in a row. Therefore, he defines the score of a choreography as follows.

The score is the length of the longest contiguous segment in which every pair of adjacent elements is different.

Creating choreography is difficult. After watching Changyoung dance, Hyunwoo points out positions that should be changed. One change flips the symbol at that position: L becomes R, and R becomes L. Changyoung wants to know the score immediately after each change.

Initially, every position in Changyoung's choreography is L.

The first line contains the length N of the choreography and the number Q of changes made by Hyunwoo.

1 <= N <= 200,000, 1 <= Q <= 200,000.

Each of the next Q lines contains one position changed by Hyunwoo, in order. Positions are numbered from 1 to N.

For each change, print the score of the choreography immediately after that change, one per line.