Mirko and Slavko started taking tap dance lessons. This dance consists mostly of tapping the floor with a special kind of shoe. Since Mirko and Slavko are fast learners, they decided to come up with their own choreography.

Tap dance choreography can be described as a sequence consisting of two letters, L and R. L means that you should tap the floor with your left foot, and R with your right foot. Mirko realised that the most exciting parts of tap dancing are the ones in which you don't use the same leg twice in a row. He defined the value of a choreography as the longest subsequence of consecutive elements that doesn't contain two consecutive Ls or Rs.

As we all know, designing a choreography can be very challenging, with lots of small changes until it's done. For every alteration that Slavko does, he would like to know the current choreography value. One alteration is changing one L to R, and vice versa.

Before any alterations are made, the choreography consists only of letters L.

Input Specification

The first line of input contains two integers, the choreography length ~N~ ~(1 \leq N \leq 200\,000)~, and the number of alterations ~Q~ ~(1 \leq Q \leq 200\,000)~.

Each of the next ~Q~ lines contains an integer specifying the position that Mirko and Slavko are altering, in order of alteration.

Output Specification

The output must contain ~Q~ integers, one per line - the current values of the choreography after each alteration.

Sample Input 1

6 2
2
4

Sample Output 1

3
5

Explanation for Sample Output 1

Choreographies are: LLLLLL ~\to~ LRLLLL ~\to~ LRLRLL.

Sample Input 2

6 5
4
1
1
2
6

Sample Output 2

3
3
3
5
6