← 返回题目列表

AtCoder · tupc2023_f

F. 酒店

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

配点 : 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