CF739C 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

The first line contain single integer $ n $ ( $ 1

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

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