**Time limit:**1.00 s**Memory limit:**512 MB

Your task is to calculate the length of the longest passage without traffic lights after each addition.

**Input**

The first input line contains two integers $x$ and $n$: the length of the street and the number of sets of traffic lights.

Then, the next line contains $n$ integers $p_1,p_2,\ldots,p_n$: the position of each set of traffic lights. Each position is distinct.

**Output**

Print the length of the longest passage without traffic lights after each addition.

**Constraints**

- $1 \le x \le 10^9$

- $1 \le n \le 2 \cdot 10^5$

- $0 < p_i < x$

**Example**

Input:

`8 3`

3 6 2

Output:

`5 3 3`