У Никиты есть стек. Стек в данной задачи — структура данных, поддерживающая две операции. Операция push(x) кладет число x на верх стека, а операция pop() удаляет верхнее число из стека, то есть последнее добавленное. Если стек пустой, то операция pop() ничего не делает.
Никита сделал со стеком m операций, да забыл какие. Сейчас Никита пытается вспомнить, какие он сделал операции. Он вспоминает операции по одной. на i-м шаге он вспоминает, какой была операция, что была pi-й по очереди. Другими словами, он вспоминает операции в порядке некоторой перестановки p1, p2, ..., pm. После каждого шага Никита хочет знать, какое число лежало бы сверху стека после выполнения тех операций, что он вспомнил, в соответствующем порядке. Помогите ему!
Выходные данные
Выведите m чисел. Число i должно равняться числу на вершине стека после выполнения всех операций, которые Никита вспомнил на шагах от 1 до i. Если стек после выполнения этих операций пуст, то выведите -1.
Примечание
В первом примере, после того, как Никита вспомнил операцию на первом шаге, операция push(2) — единственная, и поэтому ответ равен 2. После того, как он вспомнил операцию pop(), которая была сделана до push(2), ответ не изменится.
Во втором примере операции следующие: push(2), push(3) и pop(). Никита вспоминает их в том порядке, в котором они были сделаны.
В третьем примере Никита вспоминает операции в обратном порядке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 1 2
1 0
|
2
2
|
|
2
|
3
1 1 2
2 1 3
3 0
|
2
3
2
|
|
3
|
5
5 0
4 0
3 1 1
2 1 1
1 1 2
|
-1
-1
-1
-1
2
|