Steps#2306
Sasha and Vasya are creating a sequence of steps. Each step can be either left (L) or right (R). They want to analyze patterns in their sequence.
The sequence is described by letters L and R, where L represents a left step and R represents a right step. Sasha noticed that the most interesting patterns are those where consecutive steps alternate between left and right. He defined the value of a sequence as the length of the longest contiguous subsequence where no two consecutive steps are the same.
Creating an optimal sequence requires many adjustments. Therefore, Vasya wants to know the value of the sequence after each modification. Each modification consists of changing a step at a particular position from L to R (or vice versa).
Initially, the sequence consists only of L steps.
The first line contains two integers (1 \le n \le 200\,000) and (1 \le q \le 200\,000) --- the length of the sequence and the number of modifications, respectively. Each of the following lines contains an integer, giving the position where a change occurs.
Print integers, one per line: the value of the sequence after each modification.
Example 1
Example 2