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

U čekaonici za cijepljenje nalazi se 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 koliki je trenutačno najdulji niz uzastopnih slobodnih mjesta.

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 ≤ 150 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 koju sjeda neka osoba, redom kojim ulaze u čekaonicu.

Izlazni podaci

Ispišite M redaka. U k-ti redak ispišite odgovor na Mirkovo pitanje (duljinu najvećeg niza uzastopnih slobodnih 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

7
4
3
2

Ulaz

9 7
9
1
5
4
8
2
3

Izlaz

8
7
3
3
2
2
2