Размещение
Ватсону поставили задачу размещения пациентов по палатам в больнице. В палате больницы N мест, которые расположены в ряд и пронумерованы от входа последовательно от 1 до N. Чтобы минимизировать заболеваемость пациентов их нужно размещать как можно дальше друг от друга или от входа, при этом запрещено перемещать их. Ватсону доступен журнал поступления и выписывания пациентов. Для каждого поступления Ватсон должен выдать место, куда следует поместить нового пациента. Для этого необходимо выбрать место, наиболее удаленное от других пациентов в больнице. Если их несколько – минимизировать количество пациентов, которые находятся наиболее близко к новому пациенту. Если и при этом возникает несколько вариантов, то нужно выбрать самое дальнее от входа место.
Входные данные
В первой строке указано два целых числа: N – количество мест в палате и Q – количество записей в больничном журнале. Далее Q строк, в каждой из которых запись из журнала: "0" – поступление, "1 X" - выписывание пациента, поступившего по записи в журнале под номером X (нумерация в журнале идет с 1 и включает как поступления, так и выписывания). Гарантируется нахождение этого пациента в больнице. Также гарантируется, что место в больнице для нового больного всегда найдется.
0 ≤ N, Q < 10^5.
Выходные данные
Вывести место для каждого поступления по журналу.