You are given a positive integer $$$n$$$ and a non-increasing sequence $$$a_i$$$ of length $$$n$$$ , satisfying $$$\forall i \in [1,n-1],a_i \ge a_{i+1}$$$.
Then, you are given a positive integer $$$m$$$, which represents the total number of operations.
There are two types of operations. The first type gives an integer $$$x$$$ satisfying $$$1 \lt x \lt n$$$ and changes $$$a_x$$$ to $$$a_{x-1}+a_{x+1}-a_x$$$.
The second type is query operation and gives an integer $$$k$$$ . Assuming the sequence is divided into $$$k$$$ segments, and the length of each segment must be at least $$$1$$$. The value of a segment is defined as the difference between the maximum element and the minimum element of the segment. You should print the mininum sum of the values of the $$$k$$$ segments for all possible ways to divide the sequence into $$$k$$$ segments.
Specifically, for each operation, you will be given the type of the operation first. If it is $$$0$$$, it means the first type of operation, and if it is $$$1$$$, it means the second type of operation. For the first type of operation, you will then be given a positive integer $$$x$$$. For the second type of operation, you will then be given a positive integer $$$k$$$.
The first line contains a positive integer $$$n$$$ $$$(3 \le n \le 10^6 )$$$, representing the length of the sequence.
The second line contains $$$n$$$ positive integers $$$a_1, a_2, ... , a_{n}$$$ $$$(1 \le a_i \le 10^9 )$$$.
The third line contains a positive integer $$$m$$$ $$$(1 \le m \le 10^6)$$$, representing the total number of operations.
Next $$$m$$$ lines, each line containing either "$$$0$$$ $$$x$$$" $$$(1 \lt x \lt n)$$$ or "$$$1$$$ $$$k$$$" $$$(1 \le k \le n )$$$, denoting an operation.
Print $$$q$$$ lines where the $$$i$$$-th line contains one integer — the answer for the $$$i$$$-th query operation.
5 30 20 18 13 2 3 1 2 0 3 1 3
17 7
