Pyramid search#11094
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 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 Doofenshmirtz, 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.
The first line contains a single integer (1 \le n \le 10^5) - the number of regions. The second line contains numbers - the heights of the regions (|h_i| \le 10^{18}).
The third line contains the number (1 \le m \le 10^5) - the number of changes. The next lines contain two integers and (1 \le x \le n, |y| \le 10^{18}) - the index of the area whose height has changed, and the new height value for this area, respectively.
Print numbers, -th of which is equal to the length of the largest suspicious segment after the -th change.
Example 1