eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Розміщення

Розміщення

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Ватсону поставили задачу розміщення пацієнтів по палатах у лікарні. У палаті лікарні N місць, які розташовано у ряд і пронумеровано від входу послідовно від 1 до N. Щоб мінімізувати захворюваність пацієнтів їх треба розміщувати якомога далі один від одного або від входу, при цьому їх заборонено переміщувати. Ватсон має доступ до журналу надходження та виписування пацієнтів. Для кожного надходження Ватсон має видати місце, куди потрібно помістити нового пацієнта. Для цього необхідно обрати місце, найбільш віддалене від інших пацієнтів у лікарні. Якщо їх декілька – мінімізувати кількість пацієнтів на одній мінімальній відстані від нового пацієнта. Якщо і при цьому виникне декілька варіантів, то треба обрати саме дальнє від входу місце.

Вхідні дані

У першому рядку вказано два цілих числа: N – кількість місць в палаті і Q – кількість записів у лікарняному журналі. Далі Q рядків, у кожному з яких запис з журналу: "0" – надходження, "1 X" - виписування пацієнта, що надійшов за записом у журналі під номером X (нумерація в журналі йде з 1 та включає як надходження, так і виписування). Гарантується присутність цього пацієнта у лікарні. Також гарантується, що місце у лікарні для нового пацієнта знайдеться завжди.

0N, Q < 10^5.

Вихідні дані

Вивести місце для кожного надходження по журналу.

Приклад

Вхідні дані #1
6 6
0
0
0
0
1 1
0
Вихідні дані #1
6
1
4
3
6