English · Original
Chinese · Translation
Formal · Original
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.
## Input
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_.
## Output
Print _m_ lines. In _i_\-th line print the maximum width of the hills after the _i_\-th addition.
[samples]
## Note
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.
Alyona 通过将小立方体堆叠在其他立方体顶部，建造了 #cf_span[n] 座塔。每个立方体的尺寸为 #cf_span[1 × 1 × 1]。一座塔是由非零数量的立方体垂直堆叠而成。这些塔彼此相邻，形成一行。
有时，Alyona 会选择一段塔，并在每座塔的顶部放置若干立方体。形式上，Alyona 选择从 #cf_span[li] 到 #cf_span[ri] 的一段塔，并在每座塔的顶部添加 #cf_span[di] 个立方体。
设序列 #cf_span[a1, a2, ..., an] 表示从左到右每座塔的高度。若存在整数 #cf_span[k]（#cf_span[l ≤ k ≤ r]）使得 #cf_span[al < al + 1 < al + 2 < ... < ak > ak + 1 > ak + 2 > ... > ar]，则称子段 #cf_span[al, al + 1, ..., ar] 为一个“山”。
在每次向从 #cf_span[li] 到 #cf_span[ri] 的塔的顶部添加 #cf_span[di] 个立方体后，Alyona 希望知道所有“山”中的最大宽度。一个“山”的宽度是其包含的塔的数量。
第一行包含单个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 3·105]）— 塔的数量。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）— 每座塔中的立方体数量。
第三行包含单个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 3·105]）— 添加操作的数量。
接下来的 #cf_span[m] 行每行包含三个整数。第 #cf_span[i] 行包含整数 #cf_span[li], #cf_span[ri] 和 #cf_span[di]（#cf_span[1 ≤ l ≤ r ≤ n], #cf_span[1 ≤ di ≤ 109]），表示 Alyona 在从 #cf_span[li] 到 #cf_span[ri] 的每座塔的顶部添加 #cf_span[di] 个立方体。
请输出 #cf_span[m] 行。在第 #cf_span[i] 行输出第 #cf_span[i] 次添加操作后所有“山”的最大宽度。
## Input
第一行包含单个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 3·105]）— 塔的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）— 每座塔中的立方体数量。第三行包含单个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 3·105]）— 添加操作的数量。接下来的 #cf_span[m] 行每行包含三个整数。第 #cf_span[i] 行包含整数 #cf_span[li], #cf_span[ri] 和 #cf_span[di]（#cf_span[1 ≤ l ≤ r ≤ n], #cf_span[1 ≤ di ≤ 109]），表示 Alyona 在从 #cf_span[li] 到 #cf_span[ri] 的每座塔的顶部添加 #cf_span[di] 个立方体。
## Output
请输出 #cf_span[m] 行。在第 #cf_span[i] 行输出第 #cf_span[i] 次添加操作后所有“山”的最大宽度。
[samples]
## Note
第一个样例如下：
在向从第一座到第三座塔的顶部各添加 #cf_span[2] 个立方体后，塔中的立方体数量变为 #cf_span[[7, 7, 7, 5, 5]]。宽度最大的“山”是 #cf_span[[7, 5]]，因此最大宽度为 #cf_span[2]。
在向第二座塔的顶部添加 #cf_span[1] 个立方体后，塔中的立方体数量变为 #cf_span[[7, 8, 7, 5, 5]]。此时宽度最大的“山”是 #cf_span[[7, 8, 7, 5]]，因此最大宽度为 #cf_span[4]。
在向第四座塔的顶部添加 #cf_span[1] 个立方体后，塔中的立方体数量变为 #cf_span[[7, 8, 7, 6, 5]]。此时宽度最大的“山”是 #cf_span[[7, 8, 7, 6, 5]]，因此最大宽度为 #cf_span[5]。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of towers.
Let $ A = (a_1, a_2, \dots, a_n) \in \mathbb{Z}^n $ be the initial height sequence of the towers.
Let $ m \in \mathbb{Z}^+ $ be the number of update operations.
Each operation is a triple $ (l_i, r_i, d_i) $, where $ 1 \leq l_i \leq r_i \leq n $, $ d_i \geq 1 $, and after the $ i $-th operation, for all $ j \in [l_i, r_i] $, we update $ a_j \leftarrow a_j + d_i $.
A **hill** is a contiguous subsequence $ (a_l, a_{l+1}, \dots, a_r) $ such that there exists an index $ k \in [l, r] $ satisfying:
$$
a_l < a_{l+1} < \cdots < a_k > a_{k+1} > \cdots > a_r
$$
The **width** of a hill is $ r - l + 1 $.
**Constraints**
1. $ 1 \leq n \leq 3 \cdot 10^5 $
2. $ 1 \leq a_i \leq 10^9 $
3. $ 1 \leq m \leq 3 \cdot 10^5 $
4. For each update: $ 1 \leq l_i \leq r_i \leq n $, $ 1 \leq d_i \leq 10^9 $
**Objective**
After each of the $ m $ updates, compute the maximum width among all hills in the current sequence $ A $.
API Response (JSON)
{
"problem": {
"name": "E. Alyona and towers",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF740E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Alyona 通过将小立方体堆叠在其他立方体顶部，建造了 #cf_span[n] 座塔。每个立方体的尺寸为 #cf_span[1 × 1 × 1]。一座塔是由非零数量的立方体垂直堆叠而成。这些塔彼此相邻，形成一行。\n\n有时，Alyona 会选择一段塔，并在每座塔的顶部放置若干立方体。形式上，Alyona 选择从 #cf_span[li] 到 #cf_span[ri] 的一段塔，并在每座塔的顶部添加...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of towers. \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $ be the initial height sequence of the towers. \nLet $ m \\in \\mathbb{Z}^+ $ b...",
"is_translate": false,
"language": "Formal"
}
]
}