Typewriter
Contest: Codeforces Round 879 (Div. 2)
Difficulty rating: 2500
Tags: brute force, math

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 < 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!

Input format:
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.

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

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
3
2 3 1
0

Example output:
1

Example input:
3
1 2 3
2
2 1
3

Example output:
0
2
1

Editorial:
Let's solve the problem if there are no requests. The key object for us will be such cells that the number in them is less than the cell index. Note that for one carriage reset, we can transfer no more than one such number. So we have a lower bound on the answer.
Let's build a graph with edges $$$i\rightarrow a[i]$$$. Then it will break up into cycles. Let's find the first position where $$$a[i] \neq i$$$, take a number from this position, shift it to $$$a[i]$$$, take a number from position $$$a[i]$$$, and so on. Then we will put the whole cycle in its place. How many carriage drops will there be? Exactly as many edges as there are such that $$$a[i] < i$$$. That is, the answer is exactly equal to the number of positions where $$$a[i] < i$$$.
Let's learn how to solve for shifts. Let's find for each cell such positions of the beginning of the array that it will satisfy $$$a[i] < i$$$ in this configuration. It is easy to see that for a particular cell, such indexes will form a segment (possibly a prefix + suffix). Let's create a separate array and add one on these segments. Then in the i-th position there will be an answer if the array starts from the i-th cell.
Now let's solve for an array flip. It is easy to see that for this you can simply maintain the entire previous structure, but with the inverted original configuration of cells. Asymptotic: $$$O(n + q)$$$.