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 \lt i\leq n$, $b_i\geq b_{i-1}$ must hold
• $c$ is non-increasing, which means that for every $1 \lt 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.

给定一个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$。

你需要构造两个长度为 $n$ 的整数序列 $b$ 和 $c$，满足以下条件：

• 对每个 $i$（$1\leq i\leq n$），有 $b_i+c_i=a_i$；
• $b$ 是非递减序列，即对每个 $1 < i\leq n$，均有 $b_i\geq b_{i-1}$；
• $c$ 是非递增序列，即对每个 $1 < i\leq n$，均有 $c_i\leq c_{i-1}$。

你需要最小化 $\max(b_i,c_i)$。换言之，你要最小化序列 $b$ 和 $c$ 中所有元素的最大值。

此外，还会有 $q$ 次修改操作，第 $i$ 次修改由三个整数 $l,r,x$ 描述：你需要将 $a_l,a_{l+1}, \ldots, a_r$ 均增加 $x$。

你需要分别求出初始序列，以及每次修改后的序列所对应的 $\max(b_i,c_i)$ 的最小可能值。

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.

第一行包含一个整数 $n$（$1\leq n\leq 10^5$）。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\leq i\leq n$，$-10^9\leq a_i\leq 10^9$）。

第三行包含一个整数 $q$（$1\leq q\leq 10^5$）。

接下来的 $q$ 行中，每行包含三个整数 $l,r,x$（$1\leq l\leq r\leq n$，$-10^9\leq x\leq 10^9$），描述一次更新操作。

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.

输出 $q+1$ 行。

在第 $i$ 行（$1 \leq i \leq q+1$），输出经过 $i-1$ 次修改后的序列对应问题的答案。

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.

在第一个测试用例中：

• 初始序列 $a = (2, -1, 7, 3)$。序列 $b=(-3,-3,5,5)$ 和 $c=(5,2,2,-2)$ 是一种可行的选择。
• 第一次变换后，$a = (2, -4, 4, 0)$。序列 $b=(-3,-3,5,5)$ 和 $c=(5,-1,-1,-5)$ 是一种可行的选择。
• 第二次变换后，$a = (2, -4, 6, 2)$。序列 $b=(-4,-4,6,6)$ 和 $c=(6,0,0,-4)$ 是一种可行的选择。