序列(seq)

Kujou Kawaii 有一个长度为 $n$ 的序列 $a$。

Kujou Kawaii 有 $Q$ 次不同的操作，操作如下：

$1\ l\ r$: 执行如下代码：

for (int i=l;i+1<=r;i++)
    if (a[i]>a[i+1])
        swap(a[i],a[i+1]);

$2\ l\ r$: 执行如下代码：

unsigned long long ans=0
for (int i=l;i<=r;i++)
    ans+=a[i];
cout<<ans<<endl;

Kujou Kawaii 迫切的想知道每一次操作二的答案。你需要帮助她解决这个问题。

第一行两个正整数 $n$, $Q$.

第二行 $n$ 个正整数，第i个数字表示 $a_i$。

接下来 $Q$ 行，每行三个数字，表示一次操作。

对于操作 $2$，一行一个数字表示答案。

9
6

测试点 $1 \sim 2$: $1 \le n,Q \le 1000$

测试点 $3 \sim 5$: $1 \le n \le 50000$, 保证序列 $a$ 的逆序对个数小于 $10^6$

测试点 $6 \sim 8$: $1 \le n \le 50000$

测试点 $9 \sim 11$: $a_i \le 1$,

测试点 $12 \sim 15$: $a_i \le 10$

测试点 $16 \sim 17$: 所有操作 $2$ 均在操作 $1$ 之后，所有操作 $1$ 满足 $l=1,r=n$

测试点 $18 \sim 21$: 所有操作 $2$ 均在操作 $1$ 之后

测试点 $22 \sim 25$: 无特殊限制

对于所有测试数据，满足 $1 \le n \le 3 \times 10^5,1 \le Q \le 4 \times 10^4,0 \le a_i \le 10^9$。

时间限制：$\texttt{10s}$

空间限制：$\texttt{512MB}$

Universal Online Judge