0261. Столовая

Имя входного файла: canteen.in
Имя выходного файла: canteen.out
Ограничение по времени: 2 s
Ограничение по памяти: 64 megabytes

Студенты - тоже люди. Им тоже нужно кушать. Для того, чтобы они не голодали, в Университете есть столовая. Но так как студентов очень много, то в столовой очень часто бывают очереди и приходится ждать. Студенты ждать не хотят, поэтому если студент наглый, то он просто встанет куда-нибудь в середину очереди и ждать ему придется намного меньше. Более формально, можно сказать следующим образом: у каждого студента есть некоторая характеристика его наглости – целое число. Когда студент приходит в очередь, он поступает следующим образом: встает в конец очереди, после чего делает так: если наглость студента, стоящего перед ним больше его наглости, тогда он успокаивается. Иначе он выгоняет студента стоящего перед ним из очереди, после чего повторяет операцию с тем, кто теперь стоит перед ним. Тот студент, которого из очереди выгнали, дожидается, пока тот, кто его выгнал, успокоится, затем встает в конец очереди и делает так, как будто он только что пришел. Если в процессе изгнания студентов из очереди дожидаться чьего-то успокоения будет сразу несколько человек, то вставать в конец очереди они будут в порядке их изгнания.

Требуется определить, в каком порядке студенты будут получать еду.

Формат входного файла

В первой строке входного файла записано число N - количество студентов, приходящих в столовую (1 ≤ N ≤ 1000). Далее записаны события (всего 2N штук), которые происходят в столовой. Каждое событие √ это число. Если оно положительно, то значит, пришел студент с такой наглостью. Если же оно равно -1, то первый студент в очереди получает еду и уходит. Всего будет N событий прихода студентов и N событий получения еды. Гарантируется, что если кто-то получает еду, то очередь в этот момент не пуста. Все наглости различны.

Формат выходного файла

Для каждого события получения еды выведите строку с числом – номером студента, который получил еду. Студенты нумеруются с 1 в порядке их появления в столовой.

Пример:

canteen.incanteen.out
4 1 2 -1 3 -1 -1 4 -1 2 3 1 4


Источник: Первенство первокурсника ПетрГУ. Осень 2006.

Обсудить       Отправить решение



Версия для печати