CF1406D.Three Sequences

You are given a sequence of $n$ integers $a_1, a_2, \ldots, a_n$ .

You have to construct two sequences of integers $b$ and $c$ with length $n$ that satisfy:

• for every $i$ ( $1\leq i\leq n$ ) $b_i+c_i=a_i$
• $b$ is non-decreasing, which means that for every $1<i\leq n$ , $b_i\geq b_{i-1}$ must hold
• $c$ is non-increasing, which means that for every $1<i\leq n$ , $c_i\leq c_{i-1}$ must hold

You have to minimize $\max(b_i,c_i)$ . In other words, you have to minimize the maximum number in sequences $b$ and $c$ .

Also there will be $q$ changes, the $i$ -th change is described by three integers $l,r,x$ . You should add $x$ to $a_l,a_{l+1}, \ldots, a_r$ .

You have to find the minimum possible value of $\max(b_i,c_i)$ for the initial sequence and for sequence after each change.

The first line contains an integer $n$ ( $1\leq n\leq 10^5$ ).

The secound line contains $n$ integers $a_1,a_2,\ldots,a_n$ ( $1\leq i\leq n$ , $-10^9\leq a_i\leq 10^9$ ).

The third line contains an integer $q$ ( $1\leq q\leq 10^5$ ).

Each of the next $q$ lines contains three integers $l,r,x$ ( $1\leq l\leq r\leq n,-10^9\leq x\leq 10^9$ ), desribing the next change.

Print $q+1$ lines.

On the $i$ -th ( $1 \leq i \leq q+1$ ) line, print the answer to the problem for the sequence after $i-1$ changes.

In the first test:

• The initial sequence $a = (2, -1, 7, 3)$ . Two sequences $b=(-3,-3,5,5),c=(5,2,2,-2)$ is a possible choice.
• After the first change $a = (2, -4, 4, 0)$ . Two sequences $b=(-3,-3,5,5),c=(5,-1,-1,-5)$ is a possible choice.
• After the second change $a = (2, -4, 6, 2)$ . Two sequences $b=(-4,-4,6,6),c=(6,0,0,-4)$ is a possible choice.