CSES - Tikku
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Sinulla on tikku, jonka pituus on xx. Teet tikkuun nn 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 xx ja nn: tikun pituus ja leikkausten määrä. Tikku kattaa välin [0,x][0,x].

Seuraavalla rivillä on nn kokonaislukua k1,k2,,knk_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

  • 2x1092 \le x \le 10^9
  • 1n1051 \le n \le 10^5
  • 0<ki<x0 < k_i < x

Esimerkki

Syöte:

10 5
3 1 8 5 6

Tuloste:

7 7 5 3 2