Alyona and towers

题意翻译

现在有$n$个数，$m$个操作，**每次区间加一个数**，对于**每一次**操作，你要找出**最长**的$\ a_l...a_r\ $，满足 $$\exists k\! \in\![l,r],a_l<a_{l+1}<a_{l+2}<...<a_k>a_{k+1}>a_{k+2}>...>a_r$$ 输出其长度。 输入： 第一行一个整数$n$，表示数的个数。 第二行$n$个整数$a_i$。 第三行一个整数$m$，表示操作个数。 下面$m$行，每行$3$个整数，$l_i,r_i,d_i$，表示将$l_i$到$r_i$的数字加$d_i$。 输出： 对于**每个**操作，输出操作完后的答案(见题意)。 样例解释： 1. 5 5 5 5 5 $\to$ 7 7 7 5 5 ，最长的是7 5，长度为2 2. 7 7 7 5 5 $\to$ 7 8 7 5 5 ，最长的是7 8 7 5 ，长度为4 3. 7 8 7 5 5 $\to$ 7 8 7 6 5 ，最长的是7 8 7 6 5 ，长度为5

题目描述

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}&lt;a_{l+1}&lt;a_{l+2}&lt;...&lt;a_{k}&gt;a_{k+1}&gt;a_{k+2}&gt;...&gt;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.

输入输出样例

输入样例 #1

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

输出样例 #1

2
4
5

说明

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