Pyramid search
Doofenshmirtz Dirty Incorporated is messing up again! Now he daily shifts the lithospheric plates of the Earth. Perry the platypus was given an important task: every day to look for the most suspicious terrain on the straight and then, of course, report it to the agency.
He has under observation n regions located on one straight line. Each region is characterized by a single number h[i] with the altitude of that region above sea level. A segment is called suspicious if there is such a section on it that the heights of sections to the left of it strictly increase, and to the right they strictly decrease. At the same time, due to the tricks of Fufelschmertz, the heights of the sections are constantly changing.
Help Perry determine the length of the longest suspect segment after each change. It is guaranteed that at any given time there are no two adjacent regions with the same height.
Input
The first line contains a single integer n (1 ≤ n ≤ 10^5) - the number of regions. The second line contains n numbers - the heights of the regions (|h[i]| ≤ 10^18).
The third line contains the number m (1 ≤ m ≤ 10^5) - the number of changes. The next m lines contain two integers x and y (1 ≤ x ≤ n, |y| ≤ 10^18) - the index of the area which height has changed, and the new height value for this area, respectively.
Output
Print m numbers, i-th of which is equal to the length of the largest suspicious segment after the i-th change.