配点 : 100 点
問題文
长度 小于或等于 1 整数序列 给出 A=(1) 。 查询是 您将获得 Q 件,请按顺序处理。
查询如下 3 类型。
在这两种情况下,每次查询处理之前的编号顺序 A 的长度 n 和A=(a_{1},a_{2},\dots,a_{n}) 。
1 x: A 是长度 它在两个方向上都与 n+1 序列 使用 (x,a_{1},a_{2},\dots,a_{n}) 置换为。2 x: A 是长度 它在两个方向上都与 2n 序列 使用 (x,a_{1},x,a_{2},\dots,x,a_{n}) 置换为。3 x: x>n 如果 -1 。 我锻炼 x\le n 如果 a_{x} 。 我锻炼
制約
- 1 \leq Q \leq 2\times 10^5
- 1\leq x\leq 10^{9}
- 至少存在一个输出查询
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
Q t_1 x_1 t_2 x_2 \vdots t_Q x_Q
在这里,t_i (1\leq i\leq Q) 是表示查询类型的整数, 满足t_i=1,2,3 。
出力
t_i=3 的查询数量为 作为 q ,q 行。 j (1\leq j\leq q) 中, 代表第j 个此类查询的答案。
入力例 1
6 1 4 3 3 1 3 3 2 2 3 3 2
出力例 1
-1 4 3
查询 1 前: A=(1)
查询 1 後: A=(4,1)
查询 2 後: A=(4,1)
查询 3 後: A=(3,4,1)
查询 4 後: A=(3,4,1)
查询 5 後: A=(3,3,3,4,3,1)
查询 6 後: A=(3,3,3,4,3,1)
。
入力例 2
8 1 8 2 5 2 5 3 7 3 8 3 9 2 3 3 1
出力例 2
5 1 -1 3