{"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 to each other, forming a row.\n\nSometimes 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.\n\nLet 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_.\n\nAfter 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\n## Input\n\nThe first line contain single integer _n_ (1 ≤ _n_ ≤ 3·105) — the number of towers.\n\nThe second line contain _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 109) — the number of cubes in each tower.\n\nThe third line contain single integer _m_ (1 ≤ _m_ ≤ 3·105) — the number of additions.\n\nThe 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\n## Output\n\nPrint _m_ lines. In _i_\\-th line print the maximum width of the hills after the _i_\\-th addition.\n\n[samples]\n\n## Note\n\nThe first sample is as follows:\n\nAfter 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.\n\nAfter 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.\n\nAfter 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.","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] 的一段塔，并在每座塔的顶部添加 #cf_span[di] 个立方体。\n\n设序列 #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] 为一个“山”。\n\n在每次向从 #cf_span[li] 到 #cf_span[ri] 的塔的顶部添加 #cf_span[di] 个立方体后，Alyona 希望知道所有“山”中的最大宽度。一个“山”的宽度是其包含的塔的数量。\n\n第一行包含单个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 3·105]）— 塔的数量。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 109]）— 每座塔中的立方体数量。\n\n第三行包含单个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 3·105]）— 添加操作的数量。\n\n接下来的 #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] 个立方体。\n\n请输出 #cf_span[m] 行。在第 #cf_span[i] 行输出第 #cf_span[i] 次添加操作后所有“山”的最大宽度。\n\n## Input\n\n第一行包含单个整数 #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] 个立方体。\n\n## Output\n\n请输出 #cf_span[m] 行。在第 #cf_span[i] 行输出第 #cf_span[i] 次添加操作后所有“山”的最大宽度。\n\n[samples]\n\n## Note\n\n第一个样例如下：\n在向从第一座到第三座塔的顶部各添加 #cf_span[2] 个立方体后，塔中的立方体数量变为 #cf_span[[7, 7, 7, 5, 5]]。宽度最大的“山”是 #cf_span[[7, 5]]，因此最大宽度为 #cf_span[2]。\n\n在向第二座塔的顶部添加 #cf_span[1] 个立方体后，塔中的立方体数量变为 #cf_span[[7, 8, 7, 5, 5]]。此时宽度最大的“山”是 #cf_span[[7, 8, 7, 5]]，因此最大宽度为 #cf_span[4]。\n\n在向第四座塔的顶部添加 #cf_span[1] 个立方体后，塔中的立方体数量变为 #cf_span[[7, 8, 7, 6, 5]]。此时宽度最大的“山”是 #cf_span[[7, 8, 7, 6, 5]]，因此最大宽度为 #cf_span[5]。","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}^+ $ be the number of update operations.  \nEach 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 $.\n\nA **hill** is a contiguous subsequence $ (a_l, a_{l+1}, \\dots, a_r) $ such that there exists an index $ k \\in [l, r] $ satisfying:  \n$$\na_l < a_{l+1} < \\cdots < a_k > a_{k+1} > \\cdots > a_r\n$$  \nThe **width** of a hill is $ r - l + 1 $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 3 \\cdot 10^5 $  \n2. $ 1 \\leq a_i \\leq 10^9 $  \n3. $ 1 \\leq m \\leq 3 \\cdot 10^5 $  \n4. For each update: $ 1 \\leq l_i \\leq r_i \\leq n $, $ 1 \\leq d_i \\leq 10^9 $\n\n**Objective**  \nAfter each of the $ m $ updates, compute the maximum width among all hills in the current sequence $ A $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF740E","tags":[],"sample_group":[["5\n5 5 5 5 5\n3\n1 3 2\n2 2 1\n4 4 1","2\n4\n5"]],"created_at":"2026-03-03 11:00:39"}}