Problem Description

给你一个长为 $n$，初始全为 $0$ 的序列，有 $n$ 次操作，每次可以：

`1 x` 表示把 $x$ 位置修改为 $1$。

`2 x` 表示查询，如果将 $x$ 位置修改为 $1$，求最大的 $i$ 满足序列位置 $1$ 到 $i-1$ 上的值均为 $1$。这里不实际上做出这一次修改。

Input

本题无多组测试数据。

第一行一个数表示 $n$。

之后 $n$ 行，每行两个数，格式如上述，表示一次修改或者查询操作。

保证 $1 \le n \le 5\times 10^6$，每次给出的 $x$ 都在 $[1,n]$ 以内。

数据范围较大，请使用效率较高的读入方式。

Output

对于每个查询操作，输出一行一个数表示答案。

10
2 4
2 3
1 1
2 1
1 1
2 2
1 3
2 10
1 2
2 5

1
1
2
3
2
4