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。