Alyona and towers
Contest: Codeforces Round 381 (Div. 1)
Difficulty rating: 2500
Tags: data structures

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 li to ri and adds di cubes on the top of them.

Let the sequence a1, a2, ..., an be the heights of the towers from left to right. Let's call as a segment of towers al, al + 1, ..., ar a hill if the following condition holds: there is integer k (l ≤ k ≤ r) such that al < al + 1 < al + 2 < ... < ak > ak + 1 > ak + 2 > ... > ar.

After each addition of di cubes on the top of the towers from li to ri, Alyona wants to know the maximum width among all hills. The width of a hill is the number of towers in it.

Input format:
The first line contain single integer n (1 ≤ n ≤ 3·105) — the number of towers.

The second line contain n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the number of cubes in each tower.

The third line contain single integer m (1 ≤ m ≤ 3·105) — the number of additions.

The next m lines contain 3 integers each. The i-th of these lines contains integers li, ri and di (1 ≤ l ≤ r ≤ n, 1 ≤ di ≤ 109), that mean that Alyona puts di cubes on the tio of each of the towers from li to ri.

Output format:
Print m lines. In i-th line print the maximum width of the hills after the i-th addition.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

Example input:
5
5 5 5 5 5
3
1 3 2
2 2 1
4 4 1

Example output:
2
4
5

Editorial:
Let's consider the difference between two adjacent elements of array: a[i] = arr[i + 1] - arr[i]. Let us add d in the segment from l to r. Then it is clear that in the array a will change no more than two values ​​(at the ends of the addition of the segment), because if l < i < r, then a[i] = arr[i + 1] + d - (arr[i] + d) = arr[i + 1] - arr[i]. Note that the answer is a sequence of positive elements of a + a sequence of negative elements of a (i.e., ... +1 +1 +1 +1 -1 -1 ..., as the mountain first increases and then decreases). To solve this problem it's enough to take the tree segments and store at each vertex response to the prefix, suffix, and the middle. Two segments [l; m] and [m + 1; r] can be merged in case sign(a[m + 1]) ≤ sign(a[m]) and they are not equal to zero.
suffix  + 1 + 1 + 1 + 1 - 1 - 1 - 1 - 1 и  - 1 - 1 - 1 - 1 can be merged with prefix  - 1 - 1 - 1 - 1
suffix  + 1 + 1 + 1 + 1 can be merged with prefix  - 1 - 1 - 1 - 1 or prefix  + 1 + 1 + 1 + 1 - 1 - 1 - 1 - 1
Author's solution: http://codeforces.com/contest/739/submission/22453451