Rikka with Bubble Sort

Bubble sort is a simple but beautiful algorithm. And this problem is a simple data structure task which is relative to bubble sort.

Rikka has an integer array $A$ of length $n$, and then she makes $m$ operations on it.

There are two types of operations:
1. 1 L R, Rikka runs the following C program on $A$.
for (int i=L;i<R;i++) if (A[i]>A[i+1]) swap(A[i], A[i+1]);
2. 2 L R, Rikka wants to know the interval sum of $[L,R]$, i.e., $\sum_{i=L}^R A_i$.

The first line contains two integers $n,m(1 \leq n \leq 10^6, 1 \leq m \leq 3 \times 10^4)$, and the second line contains $n$ integers $A_i(1 \leq A_i \leq 10^9)$.

And then $m$ lines follow, each line contains three integers $t,L,R(t \in \{1,2\}, 1 \leq L \leq R \leq n)$.

For each query, output a single line with a single integer, the answer.

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

10
6
9

2018 Multi-University Training Contest 9