As we all know, every FIFA World Cup has a mascot and every mascot has The Official Mascot Song. For the current World Cup in Brazil, the mascot is Fuleco the Armadillo and he is currently working on his song. Since he is an armadillo, his music knowledge is limited and he only knows how to play an electric guitar. Also, he writes the song in a very simple way as a sequence of n integers A₁, A₂, ..., A_n; the integer A_i denotes how hard will Fuleco strum the strings at the i-th second.

For some indices 1 <= i <= j <= n, the consecutive subsequence A_i, A_i+1, ..., A_j of a sequence A₁, A₂, ..., A_n is called a block if the following 3 conditions hold:

        1. A_i <= A_i-1 or i = 1,

        2. A_j >= A_j+1 or j = n,

        3. A_i < A_i+1 < ... < A_j.

It is not hard to see that every sequence A₁, A₂, ..., A_n consists of disjoint blocks, i.e. every element A_i belongs to exactly one block. For example, the sequence A_i = (3 4 4 5 7 3 2 3 10) consists of 4 blocks. Fuleco (since he is an armadillo) thinks that the quality of the song depends on the number of blocks in it. He constantly does some corrections to the song and asks you to tell him the current number of blocks; he cannot count them himself since (you can guess) he is an armadillo.

More precisely, you are given the starting sequence A₁, A₂, ..., A_n and q queries. Each query is one of the following two types:

    1 x y - Fuleco changes value of the x-th element of the sequence A into y, i.e. A_x := y.

    2 z - Fuleco cyclically shifts the whole sequence A_i for the z positions to the left. When some element goes over the first position, it is moved to the n-th position. For example, the query "2 3" transforms the sequence (1, 2, 3, 4, 5) into (4, 5, 1, 2, 3).

After each query you must return the number of blocks in a current sequence (song). Note that the queries occur in the given order and they change the starting sequence. Sequence A is 1-indexed.

Input

First line of input contains one integer n (2 <= n <= 200.000) – the length of starting sequence (song) A. Second line contains n space separated integers Ai - the starting sequence. Third line contains one integer q (1 <= q <= 200.000) - the number of queries. The next q lines represent the queries in the format described above.

For each i from 1 to n, it holds 1 <= Ai <= 10⁹. For each query "1 x y" it holds 1 <= x <= n, 1 <= y <= 10⁹. For each query "2 z" it holds 1 <= z <= n.

In 30% of test cases it will hold n <= 100 and q <= 100.
In 30% of test cases there will be only the queries of the first type ("1 x y").

Output

After each query you should write the number of blocks in a current sequence. Each number must be written in a new line and the order must be the same as the order of the queries in the input.

Constraints

Time limit: 1 second
Memory limit: 64 megabytes

Examples

input
9
3 4 4 5 7 3 2 3 10
4
1 8 9
1 7 5
2 6
1 2 3

output
4
3
4
5

After 1-st query, the sequence becomes (3 4 4 5 7 3 2 9 10) and has 4 blocks. After 2-nd query, the sequence becomes (3 4 4 5 7 3 5 9 10) and has 3 blocks. After 3-rd query (left cyclic shift for 6 positions), we have sequence (5 9 10 3 4 4 5 7 3) with 4 blocks. Finally, after 4-th query, the sequence becomes (5 3 10 3 4 4 5 7 3) and has 5 blocks.