Alyona and towers

2000ms

262144K

Description:

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₁, a₂, ..., 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·10⁵) — the number of towers.

The second line contain n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹) — the number of cubes in each tower.

The third line contain single integer m (1 ≤ m ≤ 3·10⁵) — 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 ≤ 10⁹), 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.

Sample Input:

Sample Output:

2
4
5

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.

Informação

Provedor Codeforces

Código CF739C