A13709 | 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.