Задача C. Выборы ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

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

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

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

Первая группа тестов проверяется в момент сдачи задачи на проверку и стоит 20 баллов. Баллы за эту группу начисляются только при прохождении всех тестов группы. Для всех тестов этой группы выполнено условие n ≤ 100 и m ≤ 100.

Вторая группа тестов проверяется в момент сдачи задачи на проверку и стоит 20 баллов. Баллы за эту группу начисляются только при прохождении всех тестов группы. Для всех тестов этой группы выполнено условие n ≤ 3 000 и m ≤ 3 000.

Третья группа тестов проверяется в момент сдачи задачи на проверку и стоит 20 баллов. Баллы за эту группу начисляются только при прохождении всех тестов группы. Для всех тестов этой группы выполнено условие ∀ a_i:a_i ≤ 5

Четвертая группа тестов проверяется после окончания олимпиады (в CATS проверка осуществляется сразу — прим. перев.) и стоит 40 баллов. Баллы за тесты этой группы начисляются пропорционально количеству пройденных тестов.

Формат входного файла

В первой строке задано количество обработанных бюллетеней n (1 ≤ n ≤ 100 000). Во второй строке через пробел заданы n целых чисел a_i (1 ≤ a_i ≤ 10⁹) — номер кандидата, за которого проголосовал человек, опустивший в урну бюллетень номер i. В третьей строке задано число m (1 ≤ m ≤ 100 000) — количество запросов. В следующих m строках заданы сами запросы в формате l_i r_i (1 ≤ l_i ≤ r_i ≤ n) — наименьший и наибольший номера бюллетеня, которые следует рассматривать при обработке этого запроса.

Формат выходного файла

Для каждого запроса в отдельной строке выведите одно число — количество бюллетеней с номерами не меньше l_i и не больше r_i, голоса на которых отданы самому популярному кандидату на этом отрезке. Самым популярным называется любой такой кандидат, за которого среди бюллетеней с подходящими номерами отдано количество голосов не меньшее, чем за любого другого кандидата среди этих же бюллетеней.

Примеры тестов

6
1 1 2 2 1 1
3
1 6
2 4
2 5

4
2
2