step
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 ‘L’s or ‘R’s.
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’.
The first line of input contains two integers, the choreography length N (1 ≤ N ≤ 200 000), and the number of alterations Q (1 ≤ Q ≤ 200 000).
Each of the next Q lines contains an integer specifying the position that Mirko and Slavko are altering, in order of alteration.
The output must contain Q integers, one per line - the current values of the choreography after each alteration.
Input 1:
6 2
2
4Output 1:
3
5Input 2:
6 5
4
1
1
2
6Output 2:
3
3
3
5
6First sample description: choreographies are: LLLLLL → LRLLLL → LRLRLL
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.