B. Yet Another Maximization Problem
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Akram likes to make you suffer subarrays so he made a problem for you.

You are given an array $$$a$$$ of length $$$n$$$ we define the value of a subbarray as the difference between the maximum and the minimum value in it. We split $$$a$$$ into subarrays, find the maximum sum of values of the subarrays of $$$a$$$ amongst all possible splits.

In a split each element should be contained in one and only one subarray.

You are given $$$q$$$ queries of two types, update queries described by $$$3$$$ integers $$$l, r, x$$$ where you should increment $$$a[i]$$$ by $$$x$$$ for all $$$l\le i \le r$$$ , formally $$$\forall i \in [l, r] \ \ a[i] := a[i] + x$$$, queries of the second type require you to output the maximum sum of values if we split $$$a$$$ optimally.

Input

In the first line two space separated integers $$$n, \ q$$$ ($$$1 \le n, q \le 10^5$$$) The second line $$$n$$$ space separated integers describing the array $$$a$$$, $$$-10^8\le a[i] \le 10^8$$$.

Then $$$q$$$ lines each of which starts with an integer $$$t (1\le t \le 2)$$$ : the type of the query, queries of type $$$1$$$ are update queries and are described by $$$3$$$ integers $$$l, r, x (1\le l \le r\le n, -10^8\le x\le 10^8)$$$. Queries of the second type require you to output the maximum sum of values if we split $$$a$$$ optimally.

Output

For each query of the second type output the maximum sum of values if we split $$$a$$$ optimally.

Scoring

subtaskconstraintsscoring
$$$1$$$the array is sorted and there are no updates$$$5$$$ pts
$$$2$$$$$$1 \le n, q \le 200$$$$$$15$$$ pts
$$$3$$$$$$1 \le n, q \le 2000$$$$$$30$$$ pts
$$$4$$$no further constraints$$$50$$$ pts

Example
Input
4 7
-1 3 -6 8
1 4 4 2
2
1 4 4 3
2
1 1 2 -1
1 1 2 -4
2
Output
20
23
23