Fish Feeding and Survival Experiment

JOI has N fishes numbered from \(1,2,\dots,N\). The size of the \(i\)th fish is given by \(A_i\). When breeding fishes, an interesting phenomenon occurs: if two fishes are adjacent (i.e. there is no other fish between them), and if one of them has a size not less than the other, then that fish may eat the other. When fish \(x\) eats fish \(y\) (with \(A_x \ge A_y\)), its size becomes \(A_x+A_y\). In the case \(A_x=A_y\) the event may occur in either direction.

JOI will conduct experiments over \(Q\) days. On the \(j\)th day one of the following actions is performed:

• Type 1: JOI feeds fish \(X_j\) some special food, which sets its size to \(Y_j\).
• Type 2: JOI selects all fishes with indices in the interval \([L_j, R_j]\) and places them in order (from left to right) into an aquarium. Due to the properties described above, after a series of eating events, only one fish will survive. However, the order in which the fish eat each other (subject to the rule that at any moment only adjacent fishes can interact and a fish can eat its adjacent fish if its size is not less than the other’s) can affect which fish survives. JOI is wondering: how many different fishes within the interval \([L_j,R_j]\) can possibly be the final survivor if the order of eating events is chosen arbitrarily? Note that in the experiment the indices of the fishes do not change and no two fishes eat the same fish at the same time.

Your task is to process all \(Q\) actions and for each Type 2 experiment, output the number of candidate fishes.

Important details:

• All formulas must be written in \(\LaTeX\) format (for example, $N$, $A_i$, etc.).
• The experiment is only a thought experiment—no fish are actually eaten during the process.

inputFormat

The first line contains two integers \(N\) and \(Q\) \( (1 \le N, Q \le \text{small})\). The second line contains \(N\) integers \(A_1, A_2, \dots, A_N\), representing the initial sizes of the fishes.

Then \(Q\) lines follow. Each line represents an action. An action is in one of the two formats:

• 1 X Y (Type 1): Set the size of fish \(X\) to \(Y\).
• 2 L R (Type 2): Conduct the experiment on fishes with indices in \([L, R]\) and ask for the number of fishes that can possibly be the final survivor.

All indices are 1-indexed.

outputFormat

For each action of Type 2, output a single line containing one integer: the number of candidate fishes (within the chosen interval) that can possibly be the final survivor.

sample

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

2
1
2