Državno natjecanje iz informatike 2021. / Druga podskupina (3. i 4. razred) – drugi dan natjecanja - 1. zadatak

U čekaonici je N sjedećih mjesta poredanih u niz jedno do drugog, s jednakim razmacima između susjednih mjesta.

Mjesta su označena prirodnim brojevima od 1 do N s lijeva na desno i na početku su prazna.

U čekaonicu ulazi M ljudi, jedan za drugim, i svaki sjeda na neko mjesto.

Mirko iz prikrajka promatra punjenje čekaonice i često se zapita koje je od trenutačno slobodnih mjesta “najbolje”; točnije, koje je mjesto takvo da je njegova udaljenost do najbliže osobe najveća moguća (jer se tako smanjuje mogućnost zaraze).

U slučaju da postoji više takvih sjedećih mjesta, odabire se ono koje je bliže rubu (npr. kada je N > 2, mjesto s oznakom 2 udaljeno je za jedan od ruba, kao i mjesto s oznakom N − 1).

Ako i dalje postoji više takvih mjesta, odabire se ono s najmanjom oznakom.

Napišite program koji prati punjenje čekaonice i nakon svake promjene (zauzimanja nekog mjesta) ispisuje odgovor na Mirkovo pitanje.

Ulazni podaci

U prvom su retku dva prirodna broja N i M (1 ≤ M < N ≤ 100 000), broj sjedećih mjesta te broj ljudi koji ulaze u čekaonicu.

Svaki od idućih M redaka sadrži različit prirodan broj između 1 i N koji predstavlja oznaku mjesta na koje sjeda neka osoba, redom kojim ulaze u čekaonicu.

Izlazni podaci

Ispišite M redaka. U k-ti redak ispišite odgovor na Mirkovo pitanje (oznaku “najboljeg” mjesta) za stanje u čekaonici nakon što je u nju ušlo prvih k osoba.

Primjer zadatka

Ulaz

9 4
2
5
9
7

Izlaz

9
9
7
1

Objašnjenje

Pojašnjenje prvog probnog primjera: Nakon zauzimanja mjesta 2, kao i mjesta 5, najbolje je mjesto 9 na kraju reda.

Nakon zauzimanja mjesta 9, najbolje postaje mjesto 7 (jer je od najbližeg zauzetog udaljeno za dva, a sva ostala su za jedan).

Nakon zauzimanja mjesta 7, najbolje postaje mjesto 1 (sva su udaljena za jedan od najbližeg, ali ono je najbliže rubu).

Ulaz

9 7
9
1
5
4
8
2
3

Izlaz

1
5
3
7
2
3
7

Objašnjenje

Pojašnjenje drugog probnog primjera: Komentirajmo slučaj kada su zauzeta mjesta 9, 1 i 5.

Mjesta 3 i 7 jednako su udaljena od najbližeg zauzetog (za dva), a i od ruba (za dva), pa biramo mjesto s manjom oznakom (3).

Komentirajmo još i slučaj na samom kraju, kad su preostala mjesta 6 i 7 bira se mjesto 7 jer je bliže rubu.