#P1449. QAQ和车库

QAQ和车库

Description

QAQ作为车库的管理人员,他管理的车库有以下三个特点:

1, 只有一个门

2, 长度无限长

3, 车库的宽度正好能单辆小车入库或者出库,既车库不能够并排多辆小车、

每辆进入车库的小车都一样,只是小车的价值不一样。

他老板每次询问QAQ,车库里面价值最高的小车的价值是多少,由于工作量比较大,QAQ需要你的帮忙、

Format

Input

有多组测试案例. 第一行输入一个数K,表示有K次操作(1<=K<=1,000,000).

接下来有K行,每行输入有三种形式:

1 v 表示此时车库进入一辆价值为v的小车(1<=v<1,000,000,000)

2 表示此时车库有一辆小车出库

3 表示询问小明此时车库里面价值最大的小车的价值是多少,如果车库里面没有小车,则输出-1

Output

对于每次询问,输出车库中价值最大的车,如果没有小车,则输出-1

Samples

6
1 3
1 2
1 4
3
2
3

4
3

Limitation

1s, 1024KiB for each test case.