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

Illalla lehmät palaavat navettaan lypsylle. Tehtäväsi on pitää kirjaa, mikä on numeroltaan pienin navetasta puuttuva lehmä kullakin hetkellä.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: lehmien määrä ja tapahtumien määrä. Lehmät on numeroitu kokonaisluvuin 1,2,\ldots,n.

Tämän jälkeen syötteessä on m lukua x_1,x_2,\ldots,x_m. Jokainen luku tarkoittaa, että yksi lehmä saapuu navettaan.

Alussa navetassa ei ole yhtään lehmää. Lehmä ei lähde koskaan pois navettaan tulemisen jälkeen, ja ainakin yksi lehmä ei tule koskaan navettaan.

Tuloste

Ohjelmasi tulee tulostaa jokaisen lehmän saapumisen jälkeen, mikä on pienin navetasta puuttuva lehmä.

Rajat

  • 1 \le n \le 10^9
  • 1 \le m \le 10^5
  • 1 \le x_i \le n

Esimerkki

Syöte:

10 5
2 1 6 9 3

Tuloste:

1 3 3 3 4