29769번 - 음악회

문제

단대소고 음악회가 총 $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$을 한 줄에 한 쌍씩 공백으로 구분하여 출력한다.

제한

힌트