Cinema

Cerință

La cinema, un rând de scaune este format din n locuri. Inițial, toate locurile sunt libere, dar pe parcursul a $q$ minute, unele dintre aceste locuri se vor ocupa. Mai exact, la minutul $i$, locul cu numărul $p_i$ va fi ocupat. Determinați cea mai lungă secvență continuă de locuri libere la finalul fiecăruia dintre cele $q$ minute.

Date de intrare

Pe prima linie se vor afla cele două numere $n$ și $q$. Pe a $i$-a din următoarele $q$ linii se va afla numărul $p_i$ (locul care se eliberează la minutul $i$). Se garantează că înainte de minutul $i$, locul $p_i$ este liber.

Date de ieșire

Pe linia $i$ se va afișa lungimea celei mai lungi secvențe de scaune libere la finalul minutul $i$.

Restricții și precizări

• $1 \leq n \leq 200000$
• $1 \leq q, p_i \leq n$

Exemple

Intrare

4 3
2
1
4

Ieșire

2
2
1

Intrare

4 4
1
2
3
4

Ieșire

3
2
1
0