说明

Yoshino 给了你一个长度为 $n$ 的序列，第 $i$ 项为 $a_i$。

现在 Yoshino 会对数列进行 $m$ 次操作。

操作分成两种：

• $1\ l\ r\ x$ Yoshino 把数列下标在 $[l,r]$ 区间内的数修改为了一个从 $x$ 开始公差为 $1$ 的等差数列。

• $2$ Yoshino 需要查询整个数列中的逆序对个数。逆序对的定义为数对 $(i,j)$ 满足 $i<j$ 且 $a_i>a_j$。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数，第 $i$ 个为 $a_i$。

接下来 $m$ 行，每行代表一个操作，含义见上。

输出格式

对于每次询问，一行一个整数输出答案。

3 3
3 2 1 
2 
1 1 3 1 
2 

3 
0 

提示

【样例解释】

第一次操作为询问操作，此时有 $(1,3),(2,3),(1,2)$ 三组逆序对，答案为 $3$。

第二次操作修改完成后，数列变为 $1\ 2\ 3$。

第三次操作为询问操作，此时数列中没有逆序对，故答案为 $0$。

更多样例请到这里领取。

【数据范围】

本题采用捆绑测试

对于所有的数据，$1\le n,m,a_i\le 3\times 10^4$，$1\le l\le r\le n$，$1\le x\le 3\times 10^4-r+l$。