Доставка еды

Макс и Костя работают в Яндексе и снимают квартиру недалеко от офиса. В этом же доме
снимают квартиры многие их коллеги (потому что могут).
К сожалению, с марта ребятам приходится работать из дома, так что они не могут обедать в
столовой Яндекса. Готовить ребята не умеют, так что постоянно заказывают еду в разных службах
доставки. Так же поступают и их многочисленные соседи-коллеги.
Вчера Костя заболел, так что сегодня он не работает, а весь день сидит на подоконнике и грустно
смотрит на улицу. Чтобы как-то занять себя, он следит за тем, какие доставщики еды подъезжают
к его дому. За день к дому подъехало n доставщиков, про каждого из которых Костя записал его
компанию ai (им он присвоил номера от 1 до 109
).
Так как Костя — исследователь, он не может дать пропасть этому массиву данных. Для этого
он хочет извлечь из него какую-нибудь полезную (или не очень) информацию. Например, какими
службами доставки пользуются все его коллеги. Костя собирается выяснить это следующим обра-
зом: для каждого своего сослуживца он знает период его бодрствования, так что может выяснить,
каких доставщиков он (чисто гипотетически) мог вызывать. Для j-го коллеги это были доставщи-
ки с lj -го по rj -го. Тогда для каждого коллеги Костя может определить самую вероятную службу
доставки — ту, курьеров которой было больше всего в период его бодрствования.
Во время болезни Косте нельзя пользоваться ноутбуком, поэтому он просит вас закончить его
исследование: для каждого живущего в доме сотрудника Яндекса определить самую вероятную для
него службу доставки.
Формат входных данных
В первой строке дано одно целое число n (1 6 n 6 105
) — число доставшиков, увиденных Костей
за день.
Во второй строке даны n целых чисел ai (1 6 ai 6 109
) — номера службы доставки i-го достав-
щика.
В третьей строке дано одно целое число q (1 6 q 6 105
) — количество коллег Кости.
В следующих q строках дано по два целых числа lj , rj (1 6 lj 6 rj 6 n) — отрезок доставщиков,
попадающих в период бодрствования j-го коллеги Кости.
Формат выходных данных
Выведите q целых чисел — для каждого яндексоида номер самой вероятной для него службы
доставки. Если ответов несколько, выведите любой.

0