A10757 | Alyona and towers

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_{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.

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}$ .

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