음악회

시간 제한3초메모리 제한1024 MB

요약

배열의 한 값이 바뀔 때마다 평균이 가장 큰 연속 구간을 찾아 시작 번호와 끝 번호를 출력합니다. 평균이 같으면 길이가 긴 구간을, 그다음 시작 번호가 작은 구간을 고릅니다.

난이도: 보통10점 중 6점
유형: 세그먼트 트리, 배열, 구현
정답자: 아직 제출이 없습니다

문제

단대소고 음악회는 총 $Q$ 일 동안 열린다. 연주할 수 있는 학생은 $N$ 명이며, 1번부터 $N$ 번까지 번호가 붙어 있다. 번호가 $i$ 인 학생의 실력은 $A_i$ 이다. 준혁이는 매일 음악회에서 연주할 학생을 1명 이상 골라야 한다. 음악회에는 많은 관중이 모이므로, 연주하는 학생들의 평균 실력이 최대가 되어야 한다. 평균이 같다면 학생이 많을수록 좋다. 학생 수도 같다면 연주하는 학생 번호 중 가장 작은 번호가 작을수록 좋다. 또한 연주하는 학생들의 번호는 모두 연속해야 한다.

매일 오전에 학생 1명의 실력이 변한다. 연주는 오후에 있으므로, 실력이 변한 뒤에 연주한다. 날마다 준혁이가 연주시킬 학생들의 번호를 구해보자.

입력

첫째 줄에 $N$ 이 주어진다. $(1≤N≤300\,000)$

둘째 줄에 정수 $A_1, A_2, \dots, A_N$ 이 공백으로 구분되어 주어진다. $(-10^8≤A_i≤10^8)$

셋째 줄에 $Q$ 가 주어진다. $(1≤Q≤300\,000)$

넷째 줄부터 $Q+3$ 번째 줄까지 학생 $x$ 의 실력이 $y$ 로 변했음을 뜻하는 $x$ 와 $y$ 가 공백으로 구분되어 주어진다. $(1≤x≤N$ , $-10^8≤y≤10^8)$

출력

1일부터 $Q$ 일까지 날마다 학생의 실력이 변한 뒤 준혁이가 연주시킬 학생 $l, l+1, \ldots, r-1, r$ 의 $l$ 과 $r$ 을 한 줄에 한 쌍씩, 공백으로 구분하여 출력한다.

예제2

예제 1
입력
```
3
2 1 1
3
1 1
1 2
2 2
```
예상 출력
```
1 3
1 1
1 2
```
예제 2
입력
```
3
1 1 1
3
3 2
1 2
2 2
```
예상 출력
```
3 3
1 1
1 3
```