← 返回题目列表

Codeforces · 756/C

C. 尼基塔和堆栈

中文机器翻译题面 查看原题

Nikita 有一个堆栈。本问题中的栈是一种支持两种操作的数据结构。操作push(x)将一个整数x放入栈顶,操作pop()从栈顶删除整数i。 e.最后添加的。如果堆栈为空,则 pop() 操作不执行任何操作。

Nikita 对堆栈进行了 m 次操作,但忘记了它们。现在尼基塔想要记住他们。他一一记住它们,在第i步时,他记住了他所做的第一个操作。换句话说,他按照某种排列 p1,p2,...,pm 的顺序记住操作。在每一步之后,尼基塔都想知道在按照相应的顺序执行他已经记住的操作后,堆栈顶部的整数是什么。帮助他!

输入

第一行包含整数 m (1 ≤ m ≤ 105) — Nikita 进行的操作次数。

接下来的 m 行包含 Nikita 记得的操作。第 i 行以两个整数 pi 和 ti 开头(1 ≤ pi ≤ m,ti = 0 或 ti = 1)——他记住的第 i 步操作的索引以及操作的类型。如果操作是pop(),则ti 等于0;如果操作是push(x),则ti 等于1。如果操作是push(x),则该行还包含整数xi (1 ≤ xi ≤ 106)——添加到堆栈的整数。

保证从 1 到 m 的每个整数在整数 pi 中恰好出现一次。

输出

打印 m 个整数。执行完尼基塔记住的从 1 到 i 的所有操作后,整数 i 应等于堆栈顶部的数字。如果执行完所有这些操作后堆栈为空,则打印 -1。

示例

输入 #1

2
2 1 2
1 0

输出 #1

2
2

输入 #2

3
1 1 2
2 1 3
3 0

输出 #2

2
3
2

输入 #3

5
5 0
4 0
3 1 1
2 1 1
1 1 2

输出 #3

-1
-1
-1
-1
2

注意

在第一个例子中,Nikita 记住了第一步的操作后,push(2) 操作是唯一的操作,所以答案是 2。在他记住了 push(2) 之前完成的 pop() 操作后,答案保持不变。

在第二个示例中,操作是push(2)、push(3) 和pop()。尼基塔按照表演的顺序记住了它们。

在第三个示例中,Nikita 以相反的顺序记住了操作。