\(6^{th}\) round, March \(4^{th}\), 2011

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 \le N \le 200\,000\)), and the number of alterations \(Q\) (\(1 \le Q \le 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.

First sample description: the choreographies are: LLLLLL, LRLLLL, LRLRLL.

riseoj 작성

출처 COCI 2010/2011 Contest 6