× AC 后请勿重新提交,最终分数以最后一次 AC 时间为准~

毒瘤数据结构题

Accepts: 937
Submissions: 3725
Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 196608/196608 K (Java/Others)
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
对于每个查询操作,输出一行一个数表示答案。
Sample Input
10
2 4
2 3
1 1
2 1
1 1
2 2
1 3
2 10
1 2
2 5
Sample Output
1
1
2
3
2
4