CF1834F.Typewriter

Recently, Polycarp was given an unusual typewriter as a gift! Unfortunately, the typewriter was defective and had a rather strange design.

The typewriter consists of $n$ cells numbered from left to right from $1$ to $n$, and a carriage that moves over them. The typewriter cells contain $n$ distinct integers from $1$ to $n$, and each cell $i$ initially contains the integer $p_i$. Before all actions, the carriage is at cell number $1$ and there is nothing in its buffer storage. The cell on which the carriage is located is called the current cell.

The carriage can perform five types of operations:

• Take the integer from the current cell, if it is not empty, and put it in the carriage buffer, if it is empty (this buffer can contain no more than one integer).
• Put the integer from the carriage buffer, if it is not empty, into the current cell, if it is empty.
• Swap the number in the carriage buffer with the number in the current cell, if both the buffer and the cell contain integers.
• Move the carriage from the current cell $i$ to cell $i + 1$ (if $i \lt n$), while the integer in the buffer is preserved.
• Reset the carriage, i.e. move it to cell number $1$, while the integer in the buffer is preserved.

Polycarp was very interested in this typewriter, so he asks you to help him understand it and will ask you $q$ queries of three types:

1. Perform a cyclic shift of the sequence $p$ to the left by $k_j$.
2. Perform a cyclic shift of the sequence $p$ to the right by $k_j$.
3. Reverse the sequence $p$.

Before and after each query, Polycarp wants to know what minimum number of carriage resets is needed for the current sequence in order to distribute the numbers to their cells (so that the number $i$ ends up in cell number $i$).

Note that Polycarp only wants to know the minimum number of carriage resets required to arrange the numbers in their places, but he does not actually distribute them.

Help Polycarp find the answers to his queries!

最近，Polycarp 收到一台奇特的打字机作为礼物！遗憾的是，这台打字机存在缺陷，其设计相当怪异。

该打字机由 $n$ 个从左至右编号为 $1$ 到 $n$ 的单元格，以及一个在这些单元格上移动的滑架（carriage）组成。打字机的每个单元格中包含 $1$ 到 $n$ 中互不相同的整数，且初始时单元格 $i$ 中包含整数 $p_i$。所有操作开始前，滑架位于第 $1$ 号单元格，且其缓冲区（buffer storage）为空。滑架当前所在的单元格称为当前单元格。

滑架可执行以下五种类型的操作：

• 若当前单元格非空，则从中取出整数；若滑架缓冲区为空，则将该整数放入缓冲区（该缓冲区最多只能容纳一个整数）。
• 若滑架缓冲区非空，则将其所含整数放入当前单元格（仅当当前单元格为空时）。
• 若滑架缓冲区和当前单元格均含有整数，则交换二者中的数字。
• 将滑架从当前单元格 $i$ 移动至单元格 $i + 1$（要求 $i \lt n$），缓冲区中的整数保持不变。
• 重置滑架：即将滑架移回第 $1$ 号单元格，缓冲区中的整数保持不变。

Polycarp 对这台打字机非常感兴趣，因此他请你协助理解其工作原理，并将向你提出 $q$ 个查询，每种查询有以下三类之一：

1. 将序列 $p$ 向左循环移动 $k_j$ 位。
2. 将序列 $p$ 向右循环移动 $k_j$ 位。
3. 将序列 $p$ 翻转（reverse）。

在每次查询之前和之后，Polycarp 都想知道：为使当前序列满足“数字 $i$ 最终位于第 $i$ 号单元格”这一目标，所需的滑架重置操作的最小次数是多少？

注意：Polycarp 仅关心达成上述排列所需的最小重置次数，而并不实际执行这些排列操作。

请帮助 Polycarp 找出所有查询的答案！

The first line contains a single integer $n$ ($1 \le n \le 4 \cdot 10^5$) — the number of cells.

The second line contains $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) — the initial arrangement of integers in the cells.

The third line contains a single integer $q$ ($0 \le q \le 4 \cdot 10^5$) — the number of queries.

Each of the next $q$ lines describes a query from Polycarp:

The $j$-th line, at first, contains the integer $t_j$ ($1 \le t_j \le 3$) — the type of query.

If the query is of type $t_j = 1$ or $t_j = 2$, then the integer $k_j$ ($1 \le k_j \le n$) — the length of the shift — follows in the same line.

第一行包含一个整数 $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$）—— 表示移动的长度。

Output $q + 1$ numbers — the minimum number of carriage resets required before and after each of Polycarp's queries.

输出 $q + 1$ 个数字——即 Polycarp 的每次查询之前和之后所需的最小车厢重置次数。

In the first example, the answer is $1$. You can understand how the carriage works using this example.

In the second example, the sequences for which the answer needs to be calculated look like this:

1. Before all queries: $1\ 2\ 3$ — the answer is $0$.
2. After shifting to the right by $1$: $3\ 1\ 2$ — the answer is $2$.
3. After reversing the sequence: $2\ 1\ 3$ — the answer is $1$.

In the third example, the sequences before and after each query look like this:

1. $3\ 1\ 2\ 5\ 4$ — the answer is $3$.
2. $5\ 4\ 3\ 1\ 2$ — the answer is $2$.
3. $2\ 1\ 3\ 4\ 5$ — the answer is $1$.
4. $3\ 4\ 5\ 2\ 1$ — the answer is $2$.
5. $1\ 3\ 4\ 5\ 2$ — the answer is $1$.
6. $2\ 5\ 4\ 3\ 1$ — the answer is $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$。