JOI-kun 拥有 $N$ 条鱼，编号为 $1$ 到 $N$。第 $i$ 条鱼（$1 \le i \le N$）的大小为 $A_i$。

在养鱼时，我们需要注意以下事实：如果有两条相邻的鱼，随着时间的推移，其中一条鱼会吃掉另一条。这里，如果两条鱼之间没有其他鱼，则称这两条鱼是相邻的。更准确地说，如果鱼 $x$ 的大小大于或等于鱼 $y$ 的大小，且鱼 $x$ 和鱼 $y$ 相邻，那么鱼 $x$ 会吃掉鱼 $y$，并且 $x$ 的大小变为 $x$ 原本的大小与 $y$ 的大小之和。如果鱼 $x$ 和鱼 $y$ 大小相同，则其中任意一条都可以吃掉另一条。

JOI-kun 将养鱼 $Q$ 天。为了消磨时间，他进行了以下思想实验。在第 $j$ 天（$1 \le j \le Q$），JOI-kun 执行以下操作之一：

• 类型 1：JOI-kun 给鱼 $X_j$ 喂食特殊饲料。之后，鱼 $X_j$ 的大小变为 $Y_j$。
• 类型 2：JOI-kun 只取编号在 $L_j$ 到 $R_j$ 之间（包含边界）的鱼。然后 JOI-kun 进行以下思想实验： JOI-kun 将鱼 $L_j, L_j + 1, \dots, R_j$ 从左到右放入水族箱中。根据上述鱼的特性，水族箱中最终只会剩下一条鱼。幸存鱼的编号取决于被吃掉的鱼的选择以及鱼吃掉另一条鱼的时间。JOI-kun 想知道幸存鱼的可能编号数量。在思想实验过程中，鱼的顺序不会改变，且没有两条鱼会同时吃掉同一条鱼。

编写一个程序，给定 JOI-kun 的鱼的信息和 JOI-kun 的计划，计算每次类型 2 操作中幸存鱼的可能编号数量，以确定 JOI-kun 的想法是否正确。注意，这只是一个思想实验。请放心，实际上没有鱼被吃掉。

输入格式

从标准输入读取以下数据。给定值均为整数。

$N$ $A_1 \ A_2 \ \dots \ A_N$ $Q$ (查询 1) (查询 2) $\vdots$ (查询 $Q$)

每个 (查询 $j$) ($1 \le j \le Q$) 由空格分隔的整数组成。设 $T_j$ 为 (查询 $j$) 的第一个整数。该行的内容为以下之一：

• 如果 $T_j = 1$，该行包含另外两个空格分隔的整数 $X_j, Y_j$。这意味着 JOI-kun 在第 $j$ 天执行类型 1 操作。鱼 $X_j$ 的大小变为 $Y_j$。
• 如果 $T_j = 2$，该行包含另外两个空格分隔的整数 $L_j, R_j$。这意味着 JOI-kun 在第 $j$ 天执行类型 2 操作。JOI-kun 对编号在 $L_j$ 到 $R_j$ 之间的鱼进行思想实验。

输出格式

对于每次类型 2 的操作（即对于每个 $T_j = 2$ 的 $j$ ($1 \le j \le Q$)），按顺序将幸存鱼的可能编号数量输出到标准输出。输出应以换行符分隔。

数据范围

• $1 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• $1 \le A_i \le 1\,000\,000\,000 \ (= 10^9)$ ($1 \le i \le N$)
• $T_j$ 为 $1$ 或 $2$ ($1 \le j \le Q$)
• $1 \le X_j \le N$ ($1 \le j \le Q$)
• $1 \le Y_j \le 1\,000\,000\,000 \ (= 10^9)$ ($1 \le j \le Q$)
• $1 \le L_j \le R_j \le N$ ($1 \le j \le Q$)

子任务

1. (5 分) $N \le 500, Q \le 500$
2. (8 分) $Q = 1, T_j = 2, L_j = 1, R_j = N$ ($1 \le j \le Q$)
3. (12 分) $Q \le 1\,000$
4. (23 分) $T_j = 2$ ($1 \le j \le Q$)
5. (35 分) 对于每个 $T_j = 2$ 的 $j$ ($1 \le j \le Q$)，满足 $L_j = 1$ 且 $R_j = N$
6. (17 分) 无附加限制

样例

样例输入 1

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

样例输出 1

5
2
2
3
1

样例输入 2

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

样例输出 2

7

样例输入 3

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

样例输出 3

12
1
1
2
6
2
1

样例输入 4

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

4
6
1
6