{"raw_statement":[{"iden":"background","content":"JOISC2022 D4T2"},{"iden":"statement","content":"JOI 君有 $N$ 条鱼，编号为 $1,2,\\dots,N$。第 $i$ $(1 \\le i \\le N)$ 条鱼的大小为 $A_i$。\n\n当我们养鱼的时候，需要注意如下的一个事实：如果有两条鱼离得很近，那么随着时间的流逝，可能会有其中一条吃掉另一条。其中，两条鱼离得很近，当且仅当它们中间没有鱼。  \n更具体地，如果鱼 $x$ 的大小不小于鱼 $y$ 的大小，且鱼 $x,y$ 离得很近，那么 $x$ 可以吃掉 $y$，且 $x$ 的大小变为原来 $x,y$ 的大小之和。如果 $x,y$ 一样大，那么 $x$ 吃掉 $y$ 或 $y$ 吃掉 $x$ 都可能发生。\n\nJOI 君会养 $Q$ 天鱼。为了消磨时光，他会进行如下的思想实验。在第 $j$ 天 $(1 \\le j \\le Q)$，JOI 君会进行如下行动中的一个：\n\n- 第一类：JOI 君给鱼 $X_j$ 吃了某些秘制的食物。这会将鱼 $X_j$ 的大小变为 $Y_j$。\n\n- 第二类：JOI 君将编号在区间 $[L_j,R_j]$ 内的鱼单独拿出来，并进行以下实验：  \n  JOI 君将鱼 $L_j,L_j+1,\\dots,R_j$ 从左到右依次放在一个鱼缸中。由于鱼们具有如上所述的特点，最后只有一条鱼会存活。存活的这条鱼的编号取决于在哪些时刻哪些鱼吃掉了哪些鱼。JOI 君想知道可能成为最后存活者的鱼的条数。在实验中，鱼的编号不会改变，也不能有两条鱼同时吃掉同一条鱼。\n\n请写一个程序，对于给定的 JOI 君的鱼和实验的信息，计算每个第二类行动的答案来让 JOI 君能够证明或证伪自己的观点。注意这只是思想实验，并没有任何鱼真的被吃掉。"},{"iden":"input","content":"第一行，一个正整数 $N$，表示鱼的条数。\n\n第二行，$N$ 个正整数 $A_1,A_2,\\dots,A_N$，表示每条鱼的大小。\n\n第三行，一个正整数 $Q$，表示养鱼的天数。  \n接下来 $Q$ 行，其中第 $j$ $(1 \\le j \\le Q)$ 行包含若干个由空格分隔的整数，其中第一个整数为 $T_j$，表示操作类型。\n  - 若 $T_j=1$，则该行还包含两个正整数 $X_j,Y_j$，表示 JOI 君第 $j$ 天进行了第一类行动。鱼 $X_j$ 的大小变为 $Y_j$。\n  - 若 $T_j=2$，则该行还包含两个正整数 $L_j,R_j$，表示 JOI 君第 $j$ 天进行了第二类行动。JOI 君对编号在 $[L_j,R_j]$ 内的鱼进行了一次实验。"},{"iden":"output","content":"对于每次第二类行动（即，对于每个满足 $T_j=2$ 的 $j$ $(1 \\le j \\le Q)$），输出一行一个整数，表示可能成为最后存活者的鱼的条数。"},{"iden":"note","content":"**【样例解释 #1】**\n\n在 $6$ 天中，JOI 君进行了以下行动：\n\n- 第一天，他对鱼 $1,2,3,4,5$ 进行了一次实验。\n- 第二天，他对鱼 $1,2,3$ 进行了一次实验。\n- 第三天，他给鱼 $3$ 吃了秘制食物，使其大小变为 $1$。\n- 第四天，他对鱼 $2,3,4,5$ 进行了一次实验。\n- 第五天，他对鱼 $1,2,3,4,5$ 进行了一次实验。\n- 第六天，他对鱼 $2,3,4$ 进行了一次实验。\n\n第一天的实验的结果如下：\n\n- 鱼缸中的鱼的大小依次为 $[6,4,2,2,6]$。\n- 例如，经过如下过程，鱼 $2$ 会成为最后存活者。（其中粗体为鱼 $2$ 的大小。）  \n  $[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$）。\n- 类似地，鱼 $1,2,3,4,5$ 都可能成为最后存活者。因此答案为 $5$。\n\n该样例满足子任务 $1,3,6$ 的限制。\n\n**【样例解释 #2】**\n\n该样例满足所有子任务的限制。\n\n**【样例解释 #3】**\n\n该样例满足子任务 $1,3,4,6$ 的限制。\n\n**【样例解释 #4】**\n\n该样例满足子任务 $1,3,5,6$ 的限制。\n\n**【数据范围】**\n\n对于所有数据，满足：\n\n- $1 \\le N,Q \\le 100\\,000$。\n- $1 \\le A_i \\le 10^9$ $(1\\le i\\le N)$。\n- $T_j \\in \\{1,2\\}$。\n- $1 \\le X_j \\le N$ $(1\\le j\\le Q)$。\n- $1 \\le Y_j \\le 10^9$。\n- $1 \\le L_j \\le R_j \\le N$ $(1 \\le j \\le Q)$。\n\n详细子任务附加限制及分值如下表所示：\n\n|子任务编号|附加限制|分值|\n|:-:|:-:|:-:|\n|$1$|$N \\le 500$，$Q \\le 500$|$5$|\n|$2$|$Q=1$，$T_j=2$，$L_j=1$，$R_j=N$ $(1 \\le j \\le Q)$|$8$|\n|$3$|$Q\\le 1\\,000$|$12$|\n|$4$|$T_j=2$ $(1 \\le j\\le Q)$|$23$|\n|$5$|对于每个满足 $T_j=2$ 的 $j$ $(1\\le j\\le Q)$，满足 $L_j=1$，$R_j=N$|$35$|\n|$6$|无附加限制|$17$|"}],"translated_statement":null,"sample_group":[["5\n6 4 2 2 6\n6\n2 1 5\n2 1 3\n1 3 1\n2 2 5\n2 1 5\n2 2 4","5\n2\n2\n3\n1"],["13\n10 4 2 5 20 5 4 8 20 10 3 3 7\n1\n2 1 13","7"],["12\n32 32 4 1 1 1 1 4 4 16 32 128\n7\n2 1 12\n2 2 6\n2 8 10\n2 1 9\n2 3 8\n2 5 9\n2 2 12","12\n1\n1\n2\n6\n2\n1"],["10\n2 3 5 10 1 3 4 9 5 2\n8\n2 1 10\n1 10 5\n2 1 10\n1 4 1000000000\n2 1 10\n1 8 20\n1 4 8\n2 1 10","4\n6\n1\n6"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}