eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Білка та бамбук

Білка та бамбук

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Білка вирішила відправитись у кругосвітній подорож. Потрапивши у тропіки, вона виявила, що жолуді знаходити стало важче. Проте вона знайшла гарне стебло бамбука, і тепер замість того, щоб кожен день тягати жолуді по одному від одного дупла до іншого, носить їх з собою у бамбуці.

Бамбук — це трубка, один кінець якої закрито, а з іншого кінця можна класти або виймати жолуді. Діаметр трубки достатньо малий, тому якщо покласти у неї жолуді в певному порядку, виймати їх можна лише у зворотньому порядку.

Коли білка знаходить жолудь, вона відразу кладе його у бамбук. Поза те, час від часу голод заставляє білку дістати один жолудь з бамбуку і з'їсти його; із-за будови бамбуку це буде той з жолудів у ньому, який білка знайшла пізніше всього.

Білка дуже любить накопичувати жолуді в бамбуці. Тому кожен раз, коли приходиться діставати з бамбуку черговий жолудь, вона стає сумною. Проте ми знаємо, як можна її втішити! Жолуді характеризуються для білки якістю — цілим числом від 1 до 10^6. Коли білка дістала черговий жолудь, їй буде приємно знати, яке максимальне значення якості для всіх жолудів, які у бамбуці ще залишились. Ваше завдання полягає у тому, щоб вона мала таку інформацію.

Вхідні дані

У першому рядку введення міститься одне ціле число n~(1 \le n \le 10^5) — кількість подій. Кожен з наступних n рядків містить по числу, що описує подію. Якщо число додатне, то це означає, що білка знайшла жолудь і поклала його в свій бамбук. Якщо ж число дорівнює нулю, то це значить, що білка зголодніла і вийняла один жолудь з бамбука. Числа у вхідному файлі цілі і не перевищують 10^6. Гарантується, що після першого ж запиту бамбук ніколи не порожній.

Вихідні дані

Для кожного діставання жолудя з бамбуку виведіть рядок, який містить одне ціле число — максимальне значення якості для усіх жолудів, що залишились у цей момент у бамбуці.

Приклад

Вхідні дані #1
8
3
2
4
0
4
3
0
0
Вихідні дані #1
3
4
3
Автор Сергій Копеліович
Джерело Зимова Школа, Харків 2011, День 5