← 返回题目列表

Codeforces · 739/C

C. 阿廖娜和塔

中文机器翻译题面 查看原题

Alyona 通过将一些小立方体放在其他立方体的顶部来建造了 n 座塔。每个立方体的大小为 1 × 1 × 1。塔是非零数量的立方体堆叠在一起。塔楼相邻,形成一排。

有时Alyona会选择一些分段塔,并在每个塔的顶部放置几个立方体。形式上,阿尤纳选择了从 li 到 ri 的一些塔段,并在它们的顶部添加了 di 立方体。

令序列 a1, a2, ..., an 为从左到右的塔的高度。如果满足以下条件,我们将塔的一段 al, al + 1, ..., ar 称为一座山:存在整数 k (l ≤ k ≤ r) 使得 al < al + 1 < al + 2 < ... < ak > ak + 1 > ak + 2 > ... > ar。

在从 li 到 ri 的塔顶每次添加 di 立方体后,Alyona 想要知道所有山丘之间的最大宽度。一座山的宽度就是山上塔楼的数量。

输入

第一行包含单个整数 n (1 ≤ n ≤ 3·105) — 塔的数量。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) - 每个塔中的立方体数量。

第三行包含单个整数 m (1 ≤ m ≤ 3·105) — 加法次数。

接下来的 m 行每行包含 3 个整数。这些行的第 i 行包含整数 li、ri 和 di (1 ≤ l ≤ r ≤ n, 1 ≤ di ≤ 109),这意味着 Alyona 将 di 立方体放在从 li 到 ri 的每个塔的 tio 上。

输出

打印 m 行。在第 i 行中打印第 i 次添加后山丘的最大宽度。

示例

输入 #1

5
5 5 5 5 5
3
1 3 2
2 2 1
4 4 1

输出 #1

2
4
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。