No tag edit access

C. Alyona and towers

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAlyona 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*_{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}.

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^{5}) — the number of towers.

The second line contain *n* integers *a*_{1}, *a*_{2}, ..., *a*_{n} (1 ≤ *a*_{i} ≤ 10^{9}) — the number of cubes in each tower.

The third line contain single integer *m* (1 ≤ *m* ≤ 3·10^{5}) — 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^{9}), 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.

Example

Input

5

5 5 5 5 5

3

1 3 2

2 2 1

4 4 1

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.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/26/2017 19:52:39 (c2).

Desktop version, switch to mobile version.
User lists

Name |
---|