C. Alyona 与塔楼

---

每次测试的时间限制：2 秒
每次测试的内存限制：256 兆字节

---

阿廖娜通过将一些小立方体堆叠在彼此之上，建造了 $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$ 为山峰，如果存在一个整数 $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$ 个立方体之后，阿廖娜想知道所有山峰中最大的宽度。山峰的宽度即它所包含的塔的数量。

---

输入格式

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

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

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

接下来的 $m$ 行，每行包含三个整数。第 $i$ 行包含 $l_i, r_i, d_i$（$1 \le l_i \le r_i \le n$，$1 \le d_i \le 10^9$），表示阿廖娜在从 $l_i$ 到 $r_i$ 的每座塔顶部添加 $d_i$ 个立方体。

---

输出格式

输出 $m$ 行。在第 $i$ 行中，输出第 $i$ 次添加之后所有山峰的最大宽度。

---

示例

输入

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

输出

2
4
5

---

说明

第一个样例的过程如下：

1. 在第 $1$ 到第 $3$ 座塔顶部各添加 $2$ 个立方体后，各塔的立方体数量变为 $[7, 7, 7, 5, 5]$。此时宽度最大的山峰是 $[7, 5]$，因此最大宽度为 $2$。

2. 在第 $2$ 座塔顶部添加 $1$ 个立方体后，各塔的立方体数量变为 $[7, 8, 7, 5, 5]$。此时宽度最大的山峰是 $[7, 8, 7, 5]$，因此最大宽度为 $4$。

3. 在第 $4$ 座塔顶部添加 $1$ 个立方体后，各塔的立方体数量变为 $[7, 8, 7, 6, 5]$。此时宽度最大的山峰是 $[7, 8, 7, 6, 5]$，因此最大宽度为 $5$。