Three Sequences
Description
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.
Input
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.
Output
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.
Samples
4
2 -1 7 3
2
2 4 -3
3 4 2
5
5
6
6
-9 -10 -9 -6 -5 4
3
2 6 -9
1 2 -10
4 6 -3
3
3
3
1
1
0
2
1 1 -1
1 1 -1
0
0
-1
Note
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.