eolymp
bolt
Try our new interface for solving problems
Problems

Pyramid search

Pyramid search

Time limit 1 second
Memory limit 128 MiB

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 data

The first line contains a single integer n (1n10^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 (1m10^5) - the number of changes. The next m lines contain two integers x and y (1xn, |y|10^18) - the index of the area which height has changed, and the new height value for this area, respectively.

Output data

Print m numbers, i-th of which is equal to the length of the largest suspicious segment after the i-th change.

Examples

Input example #1
9
1 2 3 4 5 4 3 2 1
5
3 10
2 5
7 100000000
5 1
3 1
Output example #1
6
6
4
5
5
Source 2020 Cycle of Internet Olympiads for schoolchildren, Third team contest, Advanced level, Novemver 7, Problem C