K. 摩天大楼
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

计划建造 $$$n$$$ 座的摩天大楼在一条街道上，他们的高度从左往右将分别是 $$$h_1,~h_2,~\ldots,~h_n$$$，

$$$zy$$$ 是包工头，在每个施工阶段， $$$zy$$$ 都可以选择一个范围 $$$[l,r]$$$，然后施工队将在此范围内工作，工作结束后，第 $$$l$$$ 座到第 $$$r$$$ 座摩天大楼的高度都会增加 $$$1$$$ 。当每座摩天大楼的高度都达到（不能超过）计划高度时，这 $$$n$$$ 座摩天大楼的项目就完成了。

令 $$$zy$$$ 头疼的是，这个项目的计划总是在变，$$$zy$$$ 是个小丑，所以他请你来帮他处理以下两种操作：

  1. $$$[l, r]$$$ 区间内的计划高度增加$$$k$$$，
  2. 查询只建设 $$$[l, r]$$$ 区间的计划，即 $$$[1, l-1]$$$ , $$$[r + 1, n]$$$ 这一段计划高度均为 $$$0$$$ 的情况下,最小操作次数.
Input

第一行两个正整数 $$$n$$$和$$$m$$$.

第二行$$$n$$$个正整数，第 $$$i$$$ 个表示 $$$h_i$$$

接下来 $$$m$$$ 行，每一行的第一个数$$$p$$$表示操作，如果是 $$$p=1$$$ 就是第一种操作，然后紧接三个整数，分别表示 $$$l, r, k$$$ ，如果 是$$$p=2$$$ 就是第二种操作,紧接着两个整数表示 $$$l, r$$$。

$$$1 \le n,m \le 10^5,~1 \le h_i \le 10^6,~1 \le l \le r \le n,~p \in \{1,2\}$$$

Output

对于每次操作$$$2$$$，每行输出一个整数

Example
Input
5 4
1 3 1 4 5
2 1 5
1 3 4 2
2 2 4
2 1 5
Output
7
6
6