题目描述

题目译自 JOISC 2022 Day4 T2 「魚 2 / Fish 2」。

JOI 君有 $N$ 条鱼，编号为 $1,2,\dots,N$。第 $i$ $(1 \le i \le N)$ 条鱼的大小为 $A_i$。

当我们养鱼的时候，需要注意如下的一个事实：如果有两条鱼离得很近，那么随着时间的流逝，可能会有其中一条吃掉另一条。其中，两条鱼离得很近，当且仅当它们中间没有鱼。
更具体地，如果鱼 $x$ 的大小不小于鱼 $y$ 的大小，且鱼 $x,y$ 离得很近，那么 $x$ 可以吃掉 $y$，且 $x$ 的大小变为原来 $x,y$ 的大小之和。如果 $x,y$ 一样大，那么 $x$ 吃掉 $y$ 或 $y$ 吃掉 $x$ 都可能发生。

JOI 君会养 $Q$ 天鱼。为了消磨时光，他会进行如下的思想实验。在第 $j$ 天 $(1 \le j \le Q)$，JOI 君会进行如下行动中的一个：

• 第一类：JOI 君给鱼 $X_j$ 吃了某些秘制的食物。这会将鱼 $X_j$ 的大小变为 $Y_j$。

• 第二类：JOI 君将编号在区间 $[L_j,R_j]$ 内的鱼单独拿出来，并进行以下实验：
  JOI 君将鱼 $L_j,L_j+1,\dots,R_j$ 从左到右依次放在一个鱼缸中。由于鱼们具有如上所述的特点，最后只有一条鱼会存活。存活的这条鱼的编号取决于在哪些时刻哪些鱼吃掉了哪些鱼。JOI 君想知道可能成为最后存活者的鱼的条数。在实验中，鱼的编号不会改变，也不能有两条鱼同时吃掉同一条鱼。

请写一个程序，对于给定的 JOI 君的鱼和实验的信息，计算每个第二类行动的答案来让 JOI 君能够证明或证伪自己的观点。注意这只是思想实验，并没有任何鱼真的被吃掉。

输入格式

第一行，一个正整数 $N$，表示鱼的条数。
第二行，$N$ 个正整数 $A_1,A_2,\dots,A_N$，表示每条鱼的大小。
第三行，一个正整数 $Q$，表示养鱼的天数。
接下来 $Q$ 行，其中第 $j$ $(1 \le j \le Q)$ 行包含若干个由空格分隔的整数，其中第一个整数为 $T_j$，表示操作类型。

• 若 $T_j=1$，则该行还包含两个正整数 $X_j,Y_j$，表示 JOI 君第 $j$ 天进行了第一类行动。鱼 $X_j$ 的大小变为 $Y_j$。
• 若 $T_j=2$，则该行还包含两个正整数 $L_j,R_j$，表示 JOI 君第 $j$ 天进行了第二类行动。JOI 君对编号在 $[L_j,R_j]$ 内的鱼进行了一次实验。

输出格式

对于每次第二类行动（即，对于每个满足 $T_j=2$ 的 $j$ $(1 \le j \le Q)$），输出一行一个整数，表示可能成为最后存活者的鱼的条数。

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

5
2
2
3
1

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

7

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

12
1
1
2
6
2
1

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

4
6
1
6

数据范围与提示

对于所有数据，满足：

• $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)$。

详细子任务附加限制及分值如下表所示：