题目背景

译自 JOI Open 2025 T1「Bubble Sort Machine」/ 「バブルソート機」。

题目描述

JOI 君——一名算法工程师，开发了冒泡排序机。

冒泡排序机操作长为 $N$ 的整数序列 $a=(a_1,a_2,\ldots,a_N)$。为了让机器能工作，给定 $A_i$ 作为 $a_i$（$1\le i\le N$）的初值。每当机器上的按钮壹被按下时，机器会按照如下方式修改序列 $a$：

对于 $i=1,2,\ldots,N-1$（按此顺序），若 $a_i\gt a_{i+1}$，交换 $a_i,a_{i+1}$ 的值。

为了使冒泡排序机更博人眼球，JOI 君决定加入以下功能：

当按钮贰被按下时，给定整数 $l,r$ 作为输入（须满足 $1\le l\le r\le N$），机器会输出 $a_{l}+a_{l+1}+\cdots+a_r$ 的值。

给定整数序列的初值和冒泡排序机的操作序列，编程计算按钮贰的输出值。

输入格式

输入格式如下所示：

$N$
$A_1$ $A_2$ $\cdots$ $A_N$
$Q$
$(\text{Query }1)$
$(\text{Query }2)$
$\vdots$
$(\text{Query }Q)$

这里，$Q$ 指的是冒泡排序机的操作数。每个 $(\text{Query }j)$（$1\le j\le Q$）由若干个空格分隔的数字组成。令 $T_j$ 为 $(\text{Query }j)$ 的首个数字。这行的内容为以下二者之一：

• 若 $T_j=1$，这行再没有其他整数了。这意味着冒泡排序机的第 $j$ 次操作按下了按钮壹。
• 若 $T_j=2$，接下来还有两个整数，依次是 $L_j,R_j$。这意味着冒泡排序机的第 $j$ 次操作按下了按钮贰，给定的输入为 $L_j,R_j$。

输出格式

对每个按下按钮贰的操作［意思是，对每个满足 $T_j=2$ 的 $j$（$1\le j\le Q$）］，输出一行一个整数，表示冒泡排序机的输出。你的输出应与询问的顺序相符。

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

13
3
12
5

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

3
4
4

提示

样例解释

样例 $1$ 解释

初值为 $a_1=5,a_2=3,a_3=5,a_4=2$，$a=(5,3,5,2)$。接下来在冒泡排序机上操作：

1. 按下按钮贰，输入 $l=1,r=3$。机器输出 $a_1+a_2+a_3=13$。
2. 按下按钮壹。对 $i=1,2,3$，按此顺序进行如下操作：
   • $i=1$：由于 $a_1\gt a_2$，交换二者的值，操作后 $a=(3,5,5,2)$。
   • $i=2$：由于并没有 $a_2\gt a_3$，不操作 $a$。
   • $i=3$：由于 $a_3\gt a_4$，交换二者的值，操作后 $a=(3,5,2,5)$。
3. 按下按钮贰，输入 $l=1,r=1$。机器输出 $a_1=3$。
4. 按下按钮贰，输入 $l=2,r=4$。机器输出 $a_2+a_3+a_4=12$。
5. 按下按钮壹。对 $i=1,2,3$，按此顺序进行如下操作：
   • $i=1$：由于并没有 $a_1\gt a_2$，不操作 $a$。
   • $i=2$：由于 $a_2\gt a_3$，交换二者的值，操作后 $a=(3,2,5,5)$。
   • $i=3$：由于并没有 $a_3\gt a_4$，不操作 $a$。
6. 按下按钮贰，输入 $l=1,r=2$。机器输出 $a_1+a_2=5$。

样例 $1$ 满足子任务 $1,5,6$ 的限制。

样例 $2$ 解释

样例 $2$ 满足子任务 $1,3,5,6$ 的限制。

数据范围

• $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\in \{1,2\}\, (1\le j\le Q)$；
• 若 $T_j=2$，有 $1\le L_j\le R_j\le N\, (1\le j\le Q)$；
• 输入的值都是整数。

子任务

• $\text{Subtask 1 (5 pts)}$：满足 $T_j=1$ 的 $j\,(1\le j\le Q)$ 至多有 $10$ 个；
• $\text{Subtask 2 (11 pts)}$：$N,Q\le 150\, 000$，当 $T_j=2$ 时 $L_j=R_j=1\, (1\le j\le Q)$；
• $\text{Subtask 3 (15 pts)}$：$N,Q\le 150\, 000$，$1\le A_i\le 2\, (1\le i\le N)$；
• $\text{Subtask 4 (23 pts)}$：$N,Q\le 150\, 000$，当 $T_j=2$ 时 $L_j=R_j\, (1\le j\le Q)$；
• $\text{Subtask 5 (29 pts)}$：$N,Q\le 150\, 000$；
• $\text{Subtask 6 (17 pts)}$：无额外限制。