CF739C.Alyona and towers

Alyona has built n towers by putting small cubes some on the top of others. Each cube has size 1 × 1 × 1. A tower is a non-zero amount of cubes standing on the top of each other. The towers are next to each other, forming a row.

Sometimes Alyona chooses some segment towers, and put on the top of each tower several cubes. Formally, Alyouna chooses some segment of towers from l__i to r__i and adds d__i cubes on the top of them.

Let the sequence _a_1, _a_2, ..., a__n be the heights of the towers from left to right. Let's call as a segment of towers a__l, a__l + 1, ..., a__r a hill if the following condition holds: there is integer k (l ≤ k ≤ r) such that a__l < a__l + 1 < a__l + 2 < ... < a__k > a__k + 1 > a__k + 2 > ... > a__r.

After each addition of d__i cubes on the top of the towers from l__i to r__i, Alyona wants to know the maximum width among all hills. The width of a hill is the number of towers in it.

阿廖娜通过将小立方体堆叠在彼此之上，建成了 $n$ 座塔。每个立方体的尺寸均为 $1 \times 1 \times 1$。一座塔是由至少一个立方体垂直堆叠而成的非零高度结构。这些塔彼此相邻，排成一列。

有时，阿廖娜会选取某一段连续的塔，并在每座塔的顶部添加若干个立方体。形式化地说，她选择从第 $l_i$ 座塔到第 $r_i$ 座塔（含端点）这一区间，并在该区间内每一座塔的顶部都添加 $d_i$ 个立方体。

设序列 $a_1, a_2, \dots, a_n$ 表示从左到右各座塔的高度。我们称子段 $a_l, a_{l+1}, \dots, a_r$ 为一座“山丘”（hill），当且仅当满足如下条件：存在整数 $k$（满足 $l \le k \le r$），使得

$$a_l < a_{l+1} < a_{l+2} < \dots < a_k > a_{k+1} > a_{k+2} > \dots > a_r.$$

每次在区间 $[l_i, r_i]$ 内所有塔的顶部添加 $d_i$ 个立方体后，阿廖娜希望知道当前所有“山丘”中最大的宽度。一座“山丘”的宽度即为其所包含的塔的数量。

The first line contain single integer n (1 ≤ n ≤ 3·105) — the number of towers.

The second line contain n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109) — the number of cubes in each tower.

The third line contain single integer m (1 ≤ m ≤ 3·105) — the number of additions.

The next m lines contain 3 integers each. The i-th of these lines contains integers l__i, r__i and d__i (1 ≤ l ≤ r ≤ n, 1 ≤ d__i ≤ 109), that mean that Alyona puts d__i cubes on the tio of each of the towers from l__i to r__i.

第一行包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$）—— 塔的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）—— 每座塔中的立方体数量。

第三行包含一个整数 $m$（$1 \leq m \leq 3 \cdot 10^5$）—— 添加操作的次数。

接下来 $m$ 行，每行包含三个整数。其中第 $i$ 行包含整数 $l_i$、$r_i$ 和 $d_i$（$1 \leq l_i \leq r_i \leq n$，$1 \leq d_i \leq 10^9$），表示 Alyona 将 $d_i$ 个立方体分别加到从第 $l_i$ 座到第 $r_i$ 座的所有塔的顶端。

Print m lines. In i-th line print the maximum width of the hills after the i-th addition.

输出 m 行。在第 i 行中，输出第 i 次添加操作后山丘的最大宽度。

The first sample is as follows:

After addition of 2 cubes on the top of each towers from the first to the third, the number of cubes in the towers become equal to [7, 7, 7, 5, 5]. The hill with maximum width is [7, 5], thus the maximum width is 2.

After addition of 1 cube on the second tower, the number of cubes in the towers become equal to [7, 8, 7, 5, 5]. The hill with maximum width is now [7, 8, 7, 5], thus the maximum width is 4.

After addition of 1 cube on the fourth tower, the number of cubes in the towers become equal to [7, 8, 7, 6, 5]. The hill with maximum width is now [7, 8, 7, 6, 5], thus the maximum width is 5.

第一个样例情况如下：

在前三个塔的顶部各添加 2 个立方体后，各塔中的立方体数量变为 [7, 7, 7, 5, 5]。此时最宽的“山丘”为 [7, 5]，因此最大宽度为 2。

在第二个塔顶部添加 1 个立方体后，各塔中的立方体数量变为 [7, 8, 7, 5, 5]。此时最宽的“山丘”为 [7, 8, 7, 5]，因此最大宽度为 4。

在第四个塔顶部添加 1 个立方体后，各塔中的立方体数量变为 [7, 8, 7, 6, 5]。此时最宽的“山丘”为 [7, 8, 7, 6, 5]，因此最大宽度为 5。