N. Гоблины и очереди

Обычные гоблины встают в конец очереди. Привилегированные, знающие пароль, встают ровно в её середину, причём при нечётной длине очереди — сразу за центром.

Отследите порядок гоблинов: для каждого ухода к шаманам выведите номер уходящего.

В первой строке $N$ от $1$ до $10^5$ — количество запросов. Далее $N$ строк: + i — гоблин $i$ встаёт в конец, * i — привилегированный гоблин $i$ встаёт в середину, - — первый уходит к шаманам. Очередь в момент запроса - непуста.

Для каждого запроса - — номер уходящего гоблина, по одному на строке.