406036: GYM102220 H Skyscraper

At the main street of Byteland, there will be built $$$n$$$ skyscrapers, standing sequentially one next to other. If look leftside right, sequence of their height will be $$$a_1,a_2,\dots,a_n$$$.

Initially the street is empty, every skyscraper's height is $$$0$$$. Hamster is the leader of the construction team. In each stage, Hamster can select a range $$$[l,r]$$$, then the team will work on this range. Specifically, assume the height sequence is $$$h_1,h_2,\dots,h_n$$$, then $$$h_l,h_{l+1},\dots,h_r$$$ will increase by $$$1$$$ during this stage. When $$$h_i=a_i$$$ holds for all $$$i\in[1,n]$$$, the project will be closed.

The plan may be changed for many times. There will be $$$m$$$ events of $$$2$$$ kinds below:

• 1 l r k ($$$1\leq l\leq r\leq n,1\leq k\leq 10^5$$$), for all $$$x\in [l,r]$$$, change $$$a_x$$$ to $$$a_x+k$$$.
• 2 l r ($$$1\leq l\leq r\leq n$$$), assume $$$a_1,a_2,\dots,a_{l-1},a_{r+1},a_{r+2},\dots,a_n=0$$$, ask for the minimum number of required stages to close the project.

The first line of the input contains an integer $$$T(1\leq T\leq 1000)$$$, denoting the number of test cases.

In each test case, there are two integers $$$n,m(1\leq n,m\leq 100000)$$$ in the first line, denoting the number of skyscrapers and events.

In the second line, there are $$$n$$$ integers $$$a_1,a_2,...,a_n(1\leq a_i\leq 100000)$$$.

For the next $$$m$$$ lines, each line describes an event.

It is guaranteed that $$$\sum n\leq 10^6$$$ and $$$\sum m\leq 10^6$$$.

For each query event, print a single line containing an integer, denoting the answer.

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

7
6
6