29447번 - Выборы 다국어

문제

Недавно в стране прошли выборы, при проведении которых были использованы современные технологии: про каждый бюллетень известно, когда он был положен в урну и кандидат, за которого проголосовал человек, опустивший в урну этот бюллетень. После подсчета голосов все, кому не лень, захотели проанализировать ход выборов. Ведь не зря же вводилась вся эта система?

Многим стала интересна следующая информация: <<за какого кандидата было отдано больше всего голосов за заданный промежуток времени?>>. Ведь, если за какого-то кандидата в какой-то небольшой промежуток времени голосовали активно, а в остальное --- менее активно, то, возможно, в этот промежуток времени была совершена фальсификация. Для ответа на эти запросы даже был создан специальный сайт, на котором каждый посетитель, которому небезразлична судьба страны, мог узнать интересующую его информацию. Однако, количество посетителей оказалось неожиданно большим, и сайт перестал справляться с нагрузками.

Руководством решено было переписать все так, чтобы обслуживать одновременно $m$ пользователей. Вам поручено реализовать программу, отвечающую на вопрос, который ставят пользователи: <<За кого больше всего голосовали в данный промежуток времени?>>.

입력

В первой строке задано количество обработанных бюллетеней $n$ (1ドル \leq n \leq 100,000$). Во второй строке через пробел заданы $n$ целых чисел $a_i$ (1ドル \leq a_i \leq 10^9$) --- номер кандидата, за которого проголосовал человек, опустивший в урну бюллетень номер $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. Ололо, частичные решения