чемпионаты Спб: СПбКОШП 2023

Василий очень любит сидеть в телефоне во время поездок в метро, и очень не любит, когда кто-то из соседей видит, чем он занимается в интернете. Вася уверен, что не единственный страдает от такой проблемы, поэтому попросил вас помочь всем любителям посидеть в одиночестве.

Рассмотрим вагон метро, в котором есть один ряд из \(n\) мест, пронумерованных от \(1\) до \(n\), изначально все места свободны. Поступает \(k\) последовательных запросов. Запросы бывают двух типов:

1. «\(-x\)». Ушёл пассажир, который вошёл \(x\)-м. Гарантируется, что такой пассажир есть в вагоне.
2. «\(+\)». Пришел новый пассажир. Гарантируется, что есть хотя бы одно свободное место.

На каждый запрос второго типа следует вывести такой номер свободного места, что расстояние до ближайшего занятого — максимально. Если таких мест несколько, следует вывести место с минимальным номером. Начиная со следующего запроса это место считается занятым, до тех пор, пока его не освободят.