34351번 - 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.

서브태스크

힌트