Traffic Lights.

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 512M

Author:

Problem type

Allowed languages

Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Java, JS, Kotlin, Lisp, Lua, ObjC, OCaml, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, ~~Swift~~, TCL, Text, Turing, VB, Zig

Existe una calle de longitud $x$ ~x~ cuyas posiciones se numeran $0,1,\ldots, x$ ~0,1,\ldots, x~. Inicialmente no hay semáforos, pero $n$ ~n~ semáforos se añaden a la calle uno tras otro.

Tu tarea es calcular la longitud del tramo más largo sin semáforos después de cada adición.

Entrada

La primera línea de entrada contiene dos enteros $x$ ~x~ y $n$ ~n~: la longitud de la calle y el número de semáforos. A continuación, la siguiente línea contiene $n$ ~n~ enteros $p_1,p_2,\ldots,p_n$ ~p_1,p_2,\ldots,p_n~: la posición de cada semáforos. Cada posición es distinta.

Salida

Imprime la longitud del tramo más largo sin semáforos después de cada adición.

Restricciones

$1 \leq x \leq 10^9$ ~1 \leq x \leq 10^9~
$1 \leq n \leq 2 \cdot 10^5$ ~1 \leq n \leq 2 \cdot 10^5~
$0 < p_i < x$ ~0 < p_i < x~

Ejemplo de Entrada

8 3
3 6 2

Ejemplo de Salida

5 3 3

Comments

There are no comments at the moment.