Задача №112984. Гоблины и шаманы
Гоблины Мглистых гор очень любях ходить к своим шаманам. Так как гоблинов много, к шаманам часто образуются очень длинные очереди. А поскольку много гоблинов в одном месте быстро образуют шумную толку, которая мешает шаманам проводить сложные медицинские манипуляции, последние решили установить некоторые правила касательно порядка в очереди.
Обычные гоблины при посещении шаманов должны вставать в конец очереди. Привилегированные же гоблины, знающие особый пароль, встают ровно в ее середину, причем при нечетной длине очереди они встают сразу за центром.
Так как гоблины также широко известны своим непочтительным отношением ко всяческим правилам и законам, шаманы попросили вас написать программу, которая бы отслеживала порядок гоблинов в очереди.
Входные данные
В первой строке входных данный записано число \(N\) (\(1\le N\le 10^5\)) - количество запросов к программе. Следующие \(N\) строк содержат описание запросов в формате:
- "+ i" - гоблин с номером \(i\) (\(1\le i \le N\)) встает в конец очереди.
- "* i" - привилегированный гоблин с номером \(i\) встает в середину очереди.
- "-" - первый гоблин из очереди уходит к шаманам. Гарантируется, что на момент такого запроса очередь не пуста.
Выходные данные
Для каждого запроса типа "-" программа должна вывести номер гоблина, который должен зайти к шаманам.
7 + 1 + 2 - + 3 + 4 - -
1 2 3