说明

时间限制：1 Sec 内存限制：256 MB 输入文件：nequal.in 输出文件：nequal.out

给定长度为 $N$ 的数列 $A = \{a_1,a_2,\dots,a_N\}$。

一共给出 $Q$ 次操作，请按顺序处理所有询问，操作分为两种：

操作 1：$1$ $l$ $r$ $x$

对所有满足 $i\in[l,r]$ 的下标，执行 $a_i \leftarrow a_i + x$。

操作 2：$2$ $l$ $r$

输出 $F(l,r)$ 的值，$F(l,r)$ 定义如下：

$$ F(l, r) = \begin{cases} 1 & (l = r)\\ G(a_l, a_{l + 1}) + F(l + 1, r) & (l \lt r) \end{cases} $$

其中辅助函数 $G(x,y)$：

$$ G(x, y) = \begin{cases} 0 & (x = y)\\ 1 & (x \neq y) \end{cases} $$

函数化简说明

$F(l,r)$ 的实际含义：区间 $[l,r]$ 中相邻且数值不相等的数对的个数 $+1$。

等价：$F(l,r) = 1 + \sum_{i=l}^{r-1} G(a_i,a_{i+1})$。

输入格式

第一行两个整数 $N,Q$。

第二行 $N$ 个整数 $a_1,a_2,\dots,a_N$。

接下来 $Q$ 行，每行给出一次询问，格式为下列二者之一：

$1$ $l$ $r$ $x$

$2$ $l$ $r$

输出格式

对每一条操作 $2$，单独输出一行对应的 $F(l,r)$。

样例

样例 1

4 4
1 3 3 3
2 1 4
1 2 3 4
2 1 4
2 2 3

2
3
1

样例说明：

初始数组：$[1,3,3,3]$

查询 $F(1,4)$：相邻不等对只有 $(1,3)$，共 $1$ 对，$1+1=2$。

执行区间加：$[2,3]$ 加 $4$，数组变为 $[1,7,7,3]$

查询 $F(1,4)$：不等对为 $(1,7),(7,3)$，共 $2$ 对，$2+1=3$。

查询 $F(2,3)$：$a_2=a_3=7$，无不等对，$0+1=1$。

数据范围

对于 20% 的数据，$N,Q \le 1000$。

对于 100% 的数据，$1 \le N,Q \le 10^5$，$1 \le a_i \le 10^9$。

对于操作 1：$1 \le l \le r \le N$，$1 \le x \le 10^9$。

对于操作 2：$1 \le l \le r \le N$。

保证输入至少包含一次操作 $2$。