Description

Given a character sequence $a$ of length $n$, initially all characters in the sequence are L.

There are $q$ modifications. Each time, an integer $x$ is given. If $a_x$ is L, then change $a_x$ to R; otherwise change $a_x$ to L.

For a string $s$ consisting only of L and R, if there are no consecutive L and R in it, then $s$ is considered to satisfy the requirement.

After each modification, output the length of the longest contiguous substring in the current sequence $a$ that satisfies the requirement.

Input Format

The first line contains two integers, representing the length of the sequence $n$ and the number of modification operations $q$.

The next $q$ lines each contain one integer, representing the position $x$ to be modified in this operation.

Output Format

For each modification operation, output one integer per line, representing the length of the longest substring in the sequence $a$ that satisfies the requirement.

6 2
2
4

3
5

6 5
4
1
1
2
6

3
3
3
5
6

Hint

Constraints

For all testdata, it is guaranteed that $1 \leq n, q \leq 2 \times 10^5$, $1 \leq x \leq n$.

Notes

This problem is translated from COCI2010-2011 CONTEST #6 T5 STEP. Translation by @一扶苏一.

Translated by ChatGPT 5