Codeforces Round 879 (Div. 2) |
---|
Finished |
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:
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:
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!
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 $$$q + 1$$$ numbers — the minimum number of carriage resets required before and after each of Polycarp's queries.
3 2 3 1 0
1
3 1 2 3 2 2 1 3
0 2 1
5 3 1 2 5 4 5 1 3 3 2 3 1 4 3
3 2 1 2 1 2
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:
In the third example, the sequences before and after each query look like this:
Name |
---|