题目背景

『变成了精灵确实是遭遇了许多难过的事情，也遭遇了许多悲伤的事情。但是——我也得到了比这些难过和悲伤多得多的快乐与开心。』

『——我觉得，虽然澪小姐想要使用我的生命，但是作为交换，她不是也让我活了更长的时间了吗？』

『对了——差点忘了。四糸奈，……稍微一会儿，可以吗。』

『那么，正式介绍一下呢，——妈妈。』

『这位是七罪小姐，我——最重要的朋友。』

『这位是士道先生，是我——最喜欢的人。』

题目描述

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$。

更多样例请到这里领取。

---

【数据范围】

本题采用捆绑测试

子任务编号	$n,m\le$	特殊条件	分值	时限
$1$	$500$	无	$10$	$1s$
$2$	$3\times 10^3$		$10$	$1s$
$3$	$3\times 10^4$	修改长度为 $1$	$15$	$2s$
$4$		保证任何时刻序列中的最大值不超过 $15$	$20$
$5$		保证第奇数次操作 $1$ 为 $1\ 1\ n\ 1$	$20$	$2s$
$6$		无特殊限制	$25$	$2s$

对于所有的数据，$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$。