#P1834F. Typewriter

Typewriter

Description

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 nn cells numbered from left to right from 11 to nn, and a carriage that moves over them. The typewriter cells contain nn distinct integers from 11 to nn, and each cell ii initially contains the integer pip_i. Before all actions, the carriage is at cell number 11 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 ii to cell i+1i + 1 (if i<ni < n), while the integer in the buffer is preserved.
  • Reset the carriage, i.e. move it to cell number 11, 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 qq queries of three types:

  1. Perform a cyclic shift of the sequence pp to the left by kjk_j.
  2. Perform a cyclic shift of the sequence pp to the right by kjk_j.
  3. Reverse the sequence pp.

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 ii ends up in cell number ii).

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 nn (1n41051 \le n \le 4 \cdot 10^5) — the number of cells.

The second line contains nn distinct integers p1,p2,,pnp_1, p_2, \ldots, p_n (1pin1 \le p_i \le n) — the initial arrangement of integers in the cells.

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

Each of the next qq lines describes a query from Polycarp:

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

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

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

Input

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

The second line contains nn distinct integers p1,p2,,pnp_1, p_2, \ldots, p_n (1pin1 \le p_i \le n) — the initial arrangement of integers in the cells.

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

Each of the next qq lines describes a query from Polycarp:

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

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

Output

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

Sample Input 1

3
2 3 1
0

Sample Output 1

1

Sample Input 2

3
1 2 3
2
2 1
3

Sample Output 2

0
2
1

Sample Input 3

5
3 1 2 5 4
5
1 3
3
2 3
1 4
3

Sample Output 3

3
2
1
2
1
2

Note

In the first example, the answer is 11. 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 31\ 2\ 3 — the answer is 00.
  2. After shifting to the right by 11: 3 1 23\ 1\ 2 — the answer is 22.
  3. After reversing the sequence: 2 1 32\ 1\ 3 — the answer is 11.

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

  1. 3 1 2 5 43\ 1\ 2\ 5\ 4 — the answer is 33.
  2. 5 4 3 1 25\ 4\ 3\ 1\ 2 — the answer is 22.
  3. 2 1 3 4 52\ 1\ 3\ 4\ 5 — the answer is 11.
  4. 3 4 5 2 13\ 4\ 5\ 2\ 1 — the answer is 22.
  5. 1 3 4 5 21\ 3\ 4\ 5\ 2 — the answer is 11.
  6. 2 5 4 3 12\ 5\ 4\ 3\ 1 — the answer is 22.