Bubble Sort Machine

JOI-kun, an algorithm researcher, has developed a machine called the Bubble Sort Machine.

The Bubble Sort Machine operates on an integer sequence $a = (a_1, a_2, \dots , a_N)$ of length $N$. To activate the Bubble Sort Machine, the initial values $A_i$ are provided as input for each $a_i$ ($1 ≤ i ≤ N$). Each time Button 1 on the Bubble Sort Machine is pressed, the machine modifies the sequence $a$ in the following way:

• For each $i = 1, 2, \dots , N − 1$ in order, if $a_i > a_{i+1}$, then the values of $a_i$ and $a_{i+1}$ are swapped.

To make the Bubble Sort Machine even more appealing, JOI-kun decided to add the following feature:

• When Button 2 is pressed and integers $l$ and $r$ satisfying $1 ≤ l ≤ r ≤ N$ are given as input, the machine outputs the value of $a_l + a_{l+1} + \cdots + a_r$.

Given the initial values of the integer sequence and the sequence of operations on the Bubble Sort Machine, write a program that computes the outputs produced by Button 2.

Read the following data from the standard input.

$N$

$A_1$ $A_2$ $\cdots$ $A_N$

$Q$

(Query $1$)

(Query $2$)

$\vdots$

(Query $Q$)

Here, $Q$ is the number of operations performed on the Bubble Sort Machine. Each (Query $j$) ($1 ≤ j ≤ Q$) consists space separated integers. Let $T_j$ denote the first integer of (Query $j$). The content of this line is one of the following.

• If $T_j = 1$, this line contains no additional integers. This means that the $j$-th operation on the Bubble Sort Machine is pressing Button 1.
• If $T_j = 2$, this line contains two more integers, $L_j$ and $R_j$, in that order. This means that the $j$-th operation on the Bubble Sort Machine is pressing Button 2 with the integers $L_j$ and $R_j$ as input.

For each operation where Button 2 is pressed, that is, for each $j$ ($1 ≤ j ≤ Q$) such that $T_j = 2$, output the integer produced by the Bubble Sort Machine on a separate line in the order of the queries.

• $2 ≤ N ≤ 500\, 000$.
• $1 ≤ A_i ≤ 10^9$ ($1 ≤ i ≤ N$).
• $1 ≤ Q ≤ 500\, 000$.
• $T_j$ is either $1$ or $2$ ($1 ≤ j ≤ Q$).
• If $T_j = 2$, $1 ≤ L_j ≤ R_j ≤ N$ ($1 ≤ j ≤ Q$).
• Given values are all integers.