最近,坡旅甲收到了一台不寻常的打字机作为礼物!不幸的是,打字机有缺陷并且设计相当奇怪。
打字机由 $$$n$$$ 单元组成,从左到右从 $$$1$$$ 到 $$$n$$$ 编号,以及在单元上方移动的托架。打字机单元包含 $$$n$$$ 从 $$$1$$$ 到 $$$n$$$ 的不同整数,并且每个单元 $$$i$$$ 最初包含整数 $$$p_i$$$。在执行所有操作之前,车厢位于单元号 $$$1$$$ 处,并且其缓冲存储中没有任何内容。小车所在的单元格称为当前单元格。
笔架可以执行五种类型的操作:
- 如果当前单元格不为空,则取出整数;如果为空,则将其放入回车缓冲区(该缓冲区只能包含一个整数)。
- 将整数从回车缓冲区(如果不为空)放入当前单元格(如果为空)。
- 如果缓冲区和单元格都包含整数,则将回车缓冲区中的数字与当前单元格中的数字交换。
- 将回车从当前单元格$$$i$$$移动到单元格$$$i + 1$$$(如果$$$i < n$$$),同时保留缓冲区中的整数。
- 重置托架,即将其移动到单元格号$$$1$$$,同时保留缓冲区中的整数。
Polycarp 对这台打字机非常感兴趣,所以他要求你帮助他理解它,并会问你 $$$q$$$ 三种类型的查询:
1. 将序列 $$$p$$$ 向左循环移位 $$$k_j$$$。
2. 将序列 $$$p$$$ 向右循环移位 $$$k_j$$$。
3. 颠倒顺序$$$p$$$。
在每次查询之前和之后,Polycarp 想知道当前序列需要多少次回车重置,以便将数字分配到其单元格(以便数字 $$$i$$$ 最终出现在单元格编号 $$$i$$$ 中)。
请注意,波利卡普只想知道将数字排列在其位置所需的最小回车重置次数,但他实际上并不分发它们。
帮助波利卡普找到他的疑问的答案!
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — 单元格数量。
第二行包含 $$$n$$$ 不同的整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) - 单元格中整数的初始排列。
第三行包含一个整数 $$$q$$$ ($$$0 \le q \le 4 \cdot 10^5$$$) — 查询数。
接下来的 $$$q$$$ 行描述了来自 Polycarp 的查询:
第 $$$j$$$ 行首先包含整数 $$$t_j$$$ ($$$1 \le t_j \le 3$$$) — 查询类型。
如果查询的类型为 $$$t_j = 1$$$ 或 $$$t_j = 2$$$,则整数 $$$k_j$$$ ($$$1 \le k_j \le n$$$) — 移位的长度 — 在同一行中跟随。
输出
输出 $$$q + 1$$$ 数字 — 每次 Polycarp 查询之前和之后所需的最小回车重置次数。
示例
输入 #1
3 2 3 1 0
输出 #1
1
输入 #2
3 1 2 3 2 2 1 3
输出 #2
0 2 1
输入 #3
5 3 1 2 5 4 5 1 3 3 2 3 1 4 3
输出 #3
3 2 1 2 1 2
注意
在第一个示例中,答案是 $$$1$$$。通过这个例子,您可以了解小车的工作原理。
在第二个示例中,需要计算答案的序列如下所示:
1. 在所有查询之前:$$$1\ 2\ 3$$$ — 答案是 $$$0$$$。
2. 向右移动$$$1$$$后:$$$3\ 1\ 2$$$ — 答案是$$$2$$$。
3. 颠倒顺序后:$$$2\ 1\ 3$$$ — 答案是 $$$1$$$。
在第三个示例中,每个查询之前和之后的序列如下所示:
1. $$$3\ 1\ 2\ 5\ 4$$$ — 答案是 $$$3$$$。
2. $$$5\ 4\ 3\ 1\ 2$$$ — 答案是 $$$2$$$。
3. $$$2\ 1\ 3\ 4\ 5$$$ — 答案是 $$$1$$$。
4. $$$3\ 4\ 5\ 2\ 1$$$ — 答案是 $$$2$$$。
5. $$$1\ 3\ 4\ 5\ 2$$$ — 答案是 $$$1$$$。
6. $$$2\ 5\ 4\ 3\ 1$$$ — 答案是 $$$2$$$。