선거

최근 나라에서 최신 기술을 사용한 선거가 치러졌다. 각 투표지마다 언제 투표함에 넣었는지와 그 투표지를 넣은 사람이 투표한 후보가 기록되어 있다. 개표가 끝나자 모두가 선거가 어떻게 진행되었는지 분석하고 싶어 했다. 그러려고 이 시스템을 도입한 것이 아니겠는가?

많은 사람이 알고 싶어 한 것은 다음과 같다. 주어진 시간 구간 동안 어느 후보가 가장 많은 표를 받았는가? 짧은 구간에서 특정 후보에게 표가 몰렸고 그 밖의 시간에는 적었다면, 그 구간에서 부정이 있었을 수 있다. 이런 질문에 답하려고 사이트가 만들어졌지만, 방문자가 예상보다 많아 사이트가 부하를 감당하지 못했다.

운영진은 사이트를 동시에 $m$명의 사용자에게 서비스할 수 있도록 다시 작성하기로 했다. 여러분의 과제는 사용자가 묻는 질문, 즉 주어진 구간에서 어느 후보가 가장 많은 표를 받았는가에 답하는 프로그램을 작성하는 것이다.

첫 번째 줄에 처리한 투표지의 개수 $n$이 주어진다 ($1 \leq n \leq 100,000$).

두 번째 줄에는 공백으로 구분된 $n$개의 정수 $a_i$가 주어진다 ($1 \leq a_i \leq 10^9$). $a_i$는 투표지 번호 $i$를 투표함에 넣은 사람이 투표한 후보의 번호이다.

세 번째 줄에는 질의의 개수 $m$이 주어진다 ($1 \leq m \leq 100,000$).

이어지는 $m$개의 줄에는 각각 질의 $l_i$ $r_i$가 주어진다 ($1 \leq l_i \leq r_i \leq n$).

각 질의마다 한 줄에 하나씩, 번호가 $l_i$ 이상 $r_i$ 이하인 투표지 중 가장 인기 있는 후보의 번호를 출력한다.

그 투표지들 중에서 다른 어느 후보도 더 많은 표를 받지 못했다면, 그 후보가 가장 인기 있는 후보이다. 동률도 허용된다.

샘플의 마지막 질의에서는 답으로 1도 인정된다. ололо, 부분 점수를 받는 풀이들.