Білка вирішила відправитись у кругосвітній подорож. Потрапивши у тропіки, вона виявила, що жолуді знаходити стало важче. Проте вона знайшла гарне стебло бамбука, і тепер замість того, щоб кожен день тягати жолуді по одному від одного дупла до іншого, носить їх з собою у бамбуці. Бамбук — це трубка, один кінець якої закрито, а з іншого кінця можна класти або виймати жолуді. Діаметр трубки достатньо малий, тому якщо покласти у неї жолуді в певному порядку, виймати їх можна лише у зворотному порядку. Коли білка знаходить жолудь, вона відразу кладе його у бамбук. Поза те, час від часу голод заставляє білку дістати один жолудь з бамбуку і з'їсти його; із-за будови бамбуку це буде той з жолудів у ньому, який білка знайшла пізніше всього. Білка дуже любить накопичувати жолуді в бамбуці. Тому кожен раз, коли приходиться діставати з бамбуку черговий жолудь, вона стає сумною. Проте ми знаємо, як можна її втішити! Жолуді характеризуються для білки якістю — цілим числом від 1 до \(10^6\). Коли білка дістала черговий жолудь, їй буде приємно знати, яке максимальне значення якості для всіх жолудів, які у бамбуці ще залишились. Ваше завдання полягає у тому, щоб вона мала таку інформацію.
Формат вхідних даних
У першому рядку введення міститься одне ціле число \(n\) — кількість подій \((1 ≤ n ≤ 100000)\).
Кожен з наступних \(n\) рядків містить по числу, що описує подію. Якщо число додатне, то це означає, що білка знайшла жолудь і поклала його в свій бамбук. Якщо ж число дорівнює нулю, то це значить, що білка зголодніла і вийняла один жолудь з бамбука. Числа у вхідному файлі цілі і не перевищують \(10^6\). Гарантується, що після першого ж запиту бамбук ніколи не порожній.
Формат вихідних даних
Для кожного діставання жолудя з бамбуку виведіть рядок, який містить одне ціле число — максимальне значення якості для усіх жолудів, що залишились у цей момент у бамбуці.
Приклад вхідних даних
8
3
2
4
0
4
3
0
0
Приклад вихідних даних
3
4
3
Коментарі
додайте часу для c#
Добавив. Тепер працюємо над алгоритмом )