Задачи
Белка и бамбук
Белка и бамбук
Белка решила отправиться в кругосветное путешествие. Попав в тропики, она обнаружила, что жёлуди находить стало труднее. Зато она нашла отличный стебель бамбука, и теперь вместо того, чтобы каждый день таскать жёлуди по одному от одного дупла до другого, носит их с собой в бамбуке.
Бамбук --- это трубка, один конец которой закрыт, а с другого конца можно класть или вынимать жёлуди. Диаметр трубки достаточно мал, поэтому если положить в неё жёлуди в определённом порядке, вынимать их можно только в обратном порядке.
Когда белка находит жёлудь, она сразу кладёт его в бамбук. Кроме того, время от времени голод заставляет белку достать один жёлудь из бамбука и съесть его; из-за устройства бамбука это будет тот из желудей в нём, который белка нашла позже всего.
Белка очень любит копить жёлуди в бамбуке. Поэтому каждый раз, когда приходится доставать из бамбука очередной жёлудь, она испытывает печаль. Однако мы знаем, как можно её утешить! Жёлуди характеризуются для белки _качеством_ - целым числом от $1$ до $10^6$. Когда белка достала очередной жёлудь, ей будет приятно знать, каково максимальное значение качества для всех желудей, которые в бамбуке ещё остались. Ваша задача состоит в том, чтобы снабдить её такой информацией.
\InputFile
В первой строке ввода содержится количество событий $n~(1 \le n \le 10^5)$. Каждая из следующих $n$ строк содержит по числу, описывающему событие. Если число положительное, то оно означает, что белка нашла жёлудь и положила его в свой бамбук. Если же число равно нулю, то оно означает, что белка проголодалась и вынула один жёлудь из бамбука. Все числа целые и не превосходят $10^6$. Гарантируется, что после первого же запроса бамбук никогда не пуст.
\OutputFile
Для каждого доставания жёлудя из бамбука выведите строку, содержащую одно целое число --- максимальное значение качества для всех желудей, оставшихся в этот момент в бамбуке.
Входные данные #1
8 3 2 4 0 4 3 0 0
Выходные данные #1
3 4 3