24952번 - Fish 2 서브태스크다국어

JOI-kun has $N$ fishes, numbered from $1$ to $N$. The size of the fish $i$ ($1 ≤ i ≤ N$) is $A_i$.

When we grow fish, we have to pay attention to the following fact: if we have two nearby fishes, one fish eats the other fish as time passes. Here, two fishes are nearby if there is no fish between them. More precisely, if the size of the fish $x$ is larger than or equal to the size of the fish $y$, and the fish $x$ and the fish $y$ are nearby, then the fish $x$ eats the fish $y$, and the size of $x$ becomes the sum of the original size of $x$ and the size of $y$. If the fish $x$ and the fish $y$ have the same size, any one of them may eat the other.

JOI-kun will grow fishes for $Q$ days. To kill time, he does the following thought experiment. On the $j$-th day ($1 ≤ j ≤ Q$), JOI-kun takes one of the following actions.

• Type 1 : JOI-kun gives a special feed to the fish $X_j$. After that, the size of the fish $X_j$ becomes $Y_j$.
• Type 2 : JOI-kun takes only the fishes whose indices are between $L_j$ and $R_j$, inclusive. Then JOI-kun performs the following thought experiment: JOI-kun puts the fishes $L_j$, $L_j + 1$, $\dots$, $R_j$ into an aquarium from left to right. By the above properties of the fishes, only one fish will survive in the aquarium. The index of the surviving fish depends on the choice of eaten fishes and the time when a fish eats another fish. JOI-kun wants to know the number of possible indices of surviving fishes. During the thought experiment, the order of the fishes does not change, and no two fishes eat the same fish simultaneously.

Write a program which, given information of JOI-kun’s fishes and JOI-kun’s plan, calculates the number of possible indices of surviving fishes for each action of Type 2 in order to determine whether JOI-kun’s thought is correct or not. Note that this is just a thought experiment. Please be assured that no fishes are eaten actually.

Read the following data from the standard input. Given values are all integers.

$\begin{align*}& N \\ & A_1 \, A_2 \, \cdots \, A_N \\ & Q \\ & \text{(Query }1\text{)} \\ & \text{(Query }2\text{)} \\ & \vdots \\ & \text{(Query }Q\text{)}  \end{align*}$

Each $\text{(Query }j\text{)}$ ($1 ≤ j ≤ Q$) consists of space separated integers. Let $T_j$ be the first integer of $\text{(Query }j\text{)}$. The content of this line is one of the following.

• If $T_j = 1$, this line contains two more space separated integers $X_j$, $Y_j$, in this order. This means JOI-kun takes an action of Type 1 on $j$-th day. The size of the fish $X_j$ becomes $Y_j$.
• If $T_j = 2$, this line contains two more space separated integers $L_j$, $R_j$, in this order. This means JOI-kun takes an action of Type 2 on $j$-th day. JOI-kun performs a thought experiment for fishes whose indices are between $L_j$ and $R_j$, inclusive.

For each action of Type 2 (i.e., for each $j$ ($1 ≤ j ≤ Q$) with $T_j = 2$), in order, write the number of possible indices of surviving fishes to the standard output. The outputs should be separated by line breaks.

• $1 ≤ N ≤ 100\,000$.
• $1 ≤ Q ≤ 100\,000$.
• $1 ≤ A_i ≤ 1\,000\,000\,000$ ($= 10^9$) ($1 ≤ i ≤ N$).
• $T_j$ is either $1$ or $2$ ($1 ≤ j ≤ Q$).
• $1 ≤ X_j ≤ N$ ($1 ≤ j ≤ Q$).
• $1 ≤ Y_j ≤ 1\,000\,000\,000$ ($= 10^9$) ($1 ≤ j ≤ Q$).
• $1 ≤ L_j ≤ R_j ≤ N$ ($1 ≤ j ≤ Q$).