JOI-kun 是一位算法研究员，他开发了一台名为“冒泡排序机”的机器。

冒泡排序机对一个长度为 $N$ 的整数序列 $a = (a_1, a_2, \dots, a_N)$ 进行操作。为了启动冒泡排序机，需要输入每个 $a_i$ 的初始值 $A_i$ ($1 \le i \le N$)。每当按下冒泡排序机上的“按钮 1”时，机器会按以下方式修改序列 $a$：

对于每个 $i = 1, 2, \dots, N - 1$，按顺序执行：如果 $a_i > a_{i+1}$，则交换 $a_i$ 和 $a_{i+1}$ 的值。

为了让冒泡排序机更具吸引力，JOI-kun 决定增加以下功能：

当按下“按钮 2”并输入满足 $1 \le l \le r \le N$ 的整数 $l$ 和 $r$ 时，机器会输出 $a_l + a_{l+1} + \dots + a_r$ 的值。

给定整数序列的初始值以及冒泡排序机上的操作序列，请编写一个程序来计算“按钮 2”产生的输出。

输入格式

从标准输入读取以下数据：

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

其中，$Q$ 是在冒泡排序机上执行的操作次数。每个 (查询 $j$) ($1 \le j \le Q$) 由空格分隔的整数组成。设 $T_j$ 为 (查询 $j$) 的第一个整数。该行的内容为以下之一：

• 如果 $T_j = 1$，则该行不包含其他整数。这意味着第 $j$ 次操作是按下“按钮 1”。
• 如果 $T_j = 2$，则该行包含另外两个整数 $L_j$ 和 $R_j$。这意味着第 $j$ 次操作是按下“按钮 2”，并以 $L_j$ 和 $R_j$ 作为输入。

输出格式

对于每次按下“按钮 2”的操作，即对于每个满足 $T_j = 2$ 的 $j$ ($1 \le j \le Q$)，按查询顺序在单独的一行中输出冒泡排序机产生的结果。

数据范围

• $2 \le N \le 500\,000$
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)
• $1 \le Q \le 500\,000$
• $T_j$ 为 1 或 2 ($1 \le j \le Q$)
• 如果 $T_j = 2$，则 $1 \le L_j \le R_j \le N$ ($1 \le j \le Q$)
• 所有输入值均为整数。

子任务

1. (5 分) 满足 $T_j = 1$ 的 $j$ ($1 \le j \le Q$) 的数量最多为 10。
2. (11 分) $N \le 150\,000, Q \le 150\,000$，且当 $T_j = 2$ 时，$L_j = R_j = 1$ ($1 \le j \le Q$)。
3. (15 分) $N \le 150\,000, Q \le 150\,000, 1 \le A_i \le 2$ ($1 \le i \le N$)。
4. (23 分) $N \le 150\,000, Q \le 150\,000$，且当 $T_j = 2$ 时，$L_j = R_j$ ($1 \le j \le Q$)。
5. (29 分) $N \le 150\,000, Q \le 150\,000$。
6. (17 分) 无附加限制。

样例

样例输入 1

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

样例输出 1

13
3
12
5

说明 1

首先，给定初始值 $a_1 = 5, a_2 = 3, a_3 = 5, a_4 = 2$，初始化 $a = (5, 3, 5, 2)$。冒泡排序机的操作过程如下：

1. 按下“按钮 2”，输入 $l = 1, r = 3$。冒泡排序机输出 $a_1 + a_2 + a_3 = 13$。
2. 按下“按钮 1”。对于 $i = 1, 2, 3$，按顺序执行以下操作：
   • 对于 $i = 1$：由于 $a_1 > a_2$ 成立，交换它们的值，得到 $a = (3, 5, 5, 2)$。
   • 对于 $i = 2$：由于 $a_2 > a_3$ 不成立，不对 $a$ 进行修改。
   • 对于 $i = 3$：由于 $a_3 > a_4$ 成立，交换它们的值，得到 $a = (3, 5, 2, 5)$。
3. 按下“按钮 2”，输入 $l = 1, r = 1$。冒泡排序机输出 $a_1 = 3$。
4. 按下“按钮 2”，输入 $l = 2, r = 4$。冒泡排序机输出 $a_2 + a_3 + a_4 = 12$。
5. 按下“按钮 1”。对于 $i = 1, 2, 3$，按顺序执行以下操作：
   • 对于 $i = 1$：由于 $a_1 > a_2$ 不成立，不对 $a$ 进行修改。
   • 对于 $i = 2$：由于 $a_2 > a_3$ 成立，交换它们的值，得到 $a = (3, 2, 5, 5)$。
   • 对于 $i = 3$：由于 $a_3 > a_4$ 不成立，不对 $a$ 进行修改。
6. 按下“按钮 2”，输入 $l = 1, r = 2$。冒泡排序机输出 $a_1 + a_2 = 5$。

该样例输入满足子任务 1、5 和 6 的限制。

样例输入 2

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

样例输出 2

3
4
4

说明 2

该样例输入满足子任务 1、3、5 和 6 的限制。