Sinulla on tikku, jonka pituus on x. Teet tikkuun n leikkausta, jotka jakavat tikkua pienempiin osiin. Tehtäväsi on ilmoittaa pisimmän tikusta leikatun osan pituus joka leikkauksen jälkeen.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua x ja n: tikun pituus ja leikkausten määrä. Tikku kattaa välin [0,x].

Seuraavalla rivillä on n kokonaislukua k_1,k_2,\ldots,k_n: leikkauskohdat. Jokainen leikkaus tapahtuu eri kohdasta.

Tuloste

Ohjelmasi tulee tulostaa jokaisen leikkauksen jälkeen, mikä on pisin jäljellä oleva tikun osa.

Rajat

• 2 \le x \le 10^9
• 1 \le n \le 10^5
• 0 < k_i < x

Esimerkki

Syöte:

10 5
3 1 8 5 6

Tuloste:

7 7 5 3 2