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)$),输出一行一个整数,表示可能成为最后存活者的鱼的条数。
样例一
input
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
output
5 2 2 3 1
explanation
在 $6$ 天中,JOI 君进行了以下行动:
- 第一天,他对鱼 $1,2,3,4,5$ 进行了一次实验。
- 第二天,他对鱼 $1,2,3$ 进行了一次实验。
- 第三天,他给鱼 $3$ 吃了秘制食物,使其大小变为 $1$。
- 第四天,他对鱼 $2,3,4,5$ 进行了一次实验。
- 第五天,他对鱼 $1,2,3,4,5$ 进行了一次实验。
- 第六天,他对鱼 $2,3,4$ 进行了一次实验。
第一天的实验的结果如下:
- 鱼缸中的鱼的大小依次为 $[6,4,2,2,6]$。
- 例如,经过如下过程,鱼 $2$ 会成为最后存活者。(其中粗体为鱼 $2$ 的大小。)
$[6,\textbf 4,2,2,6]$(初始状态)$\longrightarrow$ $[6,\textbf 4,4,6]$(鱼 $4$ 吃掉鱼 $3$)$\longrightarrow$ $[6,\textbf 8,6]$(鱼 $2$ 吃掉鱼 $4$)$\longrightarrow$ $[\textbf{14},6]$(鱼 $2$ 吃掉鱼 $1$)$\longrightarrow$ $[\textbf{20}]$(鱼 $2$ 吃掉鱼 $5$)。 - 类似地,鱼 $1,2,3,4,5$ 都可能成为最后存活者。因此答案为 $5$。
该样例满足子任务 $1,3,6$ 的限制。
样例二
input
13 10 4 2 5 20 5 4 8 20 10 3 3 7 1 2 1 13
output
7
explanation
这组样例满足所有子任务的限制。
样例三
input
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
output
12 1 1 2 6 2 1
explanation
这组样例满足子任务 $1,3,4,6$ 的限制。
样例四
input
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
output
4 6 1 6
explanation
这组样例满足子任务 $1,3,5,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)$。
详细子任务附加限制及分值如下表所示:
子任务编号 | 附加限制 | 分值 |
---|---|---|
$1$ | $N \le 500$,$Q \le 500$ | $5$ |
$2$ | $Q=1$,$T_j=2$,$L_j=1$,$R_j=N$ $(1 \le j \le Q)$ | $8$ |
$3$ | $Q\le 1\,000$ | $12$ |
$4$ | $T_j=2$ $(1 \le j\le Q)$ | $23$ |
$5$ | 对于每个满足 $T_j=2$ 的 $j$ $(1\le j\le Q)$,满足 $L_j=1$,$R_j=N$ | $35$ |
$6$ | 无附加限制 | $17$ |
时间限制:$\texttt{4s}$
空间限制:$\texttt{1GB}$