Problem Description

JOI has $N$ fish, numbered $1, 2, \dots, N$. The size of the $i$-th $(1 \le i \le N)$ fish is $A_i$.

When raising fish, it is important to note the following fact: if two fish are very close to each other, one of them may eat the other over time. Specifically, two fish are very close if and only if there is no other fish between them.

More specifically, if the size of fish $x$ is not less than the size of fish $y$, and fish $x$ and $y$ are very close, then $x$ can eat $y$, and the size of $x$ becomes the sum of the sizes of $x$ and $y$. If $x$ and $y$ are of the same size, either $x$ can eat $y$ or $y$ can eat $x$.

JOI will raise fish for $Q$ days. To pass the time, he will conduct the following thought experiment. On the $j$-th day $(1 \le j \le Q)$, JOI will perform one of the following actions:

• Type 1: JOI feeds fish $X_j$ with some special food. This changes the size of fish $X_j$ to $Y_j$.

• Type 2: JOI takes out the fish with indices in the interval $[L_j, R_j]$ and conducts the following experiment:
  JOI places the fish $L_j, L_j+1, \dots, R_j$ in a tank from left to right. Due to the characteristics described above, only one fish will survive in the end. The index of the surviving fish depends on which fish ate which at what times. JOI wants to know the number of fish that could potentially be the last survivor. In the experiment, the indices of the fish do not change, and no two fish can eat the same fish simultaneously.

Write a program that, given the information about JOI's fish and experiments, calculates the answer for each Type 2 action so that JOI can prove or disprove his hypotheses. Note that this is a thought experiment, and no fish are actually eaten.

Input Format

The first line contains a positive integer $N$, the number of fish.

The second line contains $N$ positive integers $A_1, A_2, \dots, A_N$, the sizes of the fish.

The third line contains a positive integer $Q$, the number of days.

The next $Q$ lines, where the $j$-th $(1 \le j \le Q)$ line contains several space-separated integers, with the first integer being $T_j$, the type of operation.
- If $T_j=1$, the line also contains two positive integers $X_j, Y_j$, indicating that JOI performed a Type 1 action on day $j$. The size of fish $X_j$ is changed to $Y_j$.
- If $T_j=2$, the line also contains two positive integers $L_j, R_j$, indicating that JOI performed a Type 2 action on day $j$. JOI conducts an experiment on the fish with indices in $[L_j, R_j]$.

Output Format

For each Type 2 action (i.e., for each $j$ $(1 \le j \le Q)$ where $T_j=2$), output one line containing an integer, the number of fish that could potentially be the last survivor.

Sample Input and Output

Sample Input #1

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

Sample Output #1

5
2
2
3
1

Sample Input #2

13
10 4 2 5 20 5 4 8 20 10 3 3 7
1
2 1 13

Sample Output #2

7

Sample Input #3

12
32 32 4 1 1 1 1 4 4 16 32 128
7
2 1 12
2 2 6
2 8 10
2 1 9
2 3 8
2 5 9
2 2 12

Sample Output #3

12
1
1
2
6
2
1

Sample Input #4

10
2 3 5 10 1 3 4 9 5 2
8
2 1 10
1 10 5
2 1 10
1 4 1000000000
2 1 10
1 8 20
1 4 8
2 1 10

Sample Output #4

4
6
1
6

Notes/Hints

[Sample Explanation #1]

During the 6 days, JOI performs the following actions:

• On the first day, he conducts an experiment on fish $1, 2, 3, 4, 5$.
• On the second day, he conducts an experiment on fish $1, 2, 3$.
• On the third day, he feeds fish $3$ with special food, changing its size to $1$.
• On the fourth day, he conducts an experiment on fish $2, 3, 4, 5$.
• On the fifth day, he conducts an experiment on fish $1, 2, 3, 4, 5$.
• On the sixth day, he conducts an experiment on fish $2, 3, 4$.

The result of the first day's experiment is as follows:

• The sizes of the fish in the tank are $[6, 4, 2, 2, 6]$.
• For example, fish $2$ could be the last survivor through the following process (where bold indicates the size of fish $2$):
  $[6, \textbf{4}, 2, 2, 6]$ (initial state) $\longrightarrow$ $[6, \textbf{4}, 4, 6]$ (fish $4$ eats fish $3$) $\longrightarrow$ $[6, \textbf{8}, 6]$ (fish $2$ eats fish $4$) $\longrightarrow$ $[\textbf{14}, 6]$ (fish $2$ eats fish $1$) $\longrightarrow$ $[\textbf{20}]$ (fish $2$ eats fish $5$).
• Similarly, fish $1, 2, 3, 4, 5$ could all potentially be the last survivor. Thus, the answer is $5$.

This sample satisfies the constraints of subtasks $1, 3, 6$.

[Sample Explanation #2]

This sample satisfies the constraints of all subtasks.

[Sample Explanation #3]

This sample satisfies the constraints of subtasks $1, 3, 4, 6$.

[Sample Explanation #4]

This sample satisfies the constraints of subtasks $1, 3, 5, 6$.

[Data Range]

For all data, the following constraints are satisfied:

• $1 \le N, Q \le 100,000$.
• $1 \le A_i \le 10^9$ $(1 \le i \le N)$.
• $T_j \in \{1, 2\}$.
• $1 \le X_j \le N$ $(1 \le j \le Q)$.
• $1 \le Y_j \le 10^9$.
• $1 \le L_j \le R_j \le N$ $(1 \le j \le Q)$.

Detailed subtask additional constraints and scores are as follows:

见题面 Input 部分

见题面 Output 部分