Concert

Time limit3sMemory limit1024 MB

Summary

After each point update to an array, find the contiguous range with the largest average, breaking ties by longer length, then by smaller left index.

Level: Medium6 of 10
Topics: Segment tree, Array, Implementation
Solved: No attempts yet

Problem

The Dandae High School concert runs for $Q$ days. $N$ students who can perform are numbered from 1 to $N$ , and student $i$ has skill $A_i$ . Every day, Junhyuk must pick at least one student to perform. Many spectators attend the concert, so the average skill of the performing students must be as large as possible. If two groups have the same average, the group with more students is better. If the group sizes are also equal, the group whose smallest number is smaller is better. The numbers of the performing students must also be consecutive.

Every morning, the skill of one student changes. The performance is in the afternoon, so it takes place after the change. For each day, find the numbers of the students Junhyuk should have perform.

Input

The first line contains $N$ . $(1≤N≤300\,000)$

The second line contains the integers $A_1, A_2, \dots, A_N$ separated by spaces. $(-10^8≤A_i≤10^8)$

The third line contains $Q$ . $(1≤Q≤300\,000)$

From the fourth line through line $Q+3$ , each line contains $x$ and $y$ separated by a space, meaning that the skill of student $x$ changes to $y$ . $(1≤x≤N$ , $-10^8≤y≤10^8)$

Output

For each day from 1 to $Q$ , after that day's skill change, print $l$ and $r$ of the students $l, l+1, \ldots, r-1, r$ that Junhyuk makes perform. Print one pair per line, separated by a space.

Examples2

Example 1
Input
```
3
2 1 1
3
1 1
1 2
2 2
```
Expected output
```
1 3
1 1
1 2
```
Example 2
Input
```
3
1 1 1
3
3 2
1 2
2 2
```
Expected output
```
3 3
1 1
1 3
```