407266: GYM102739 H Доставка еды

H. Доставка едыограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Макс и Костя работают в Яндексе и снимают квартиру недалеко от офиса. В этом же доме снимают квартиры многие их коллеги (потому что могут).

К сожалению, с марта ребятам приходится работать из дома, так что они не могут обедать в столовой Яндекса. Готовить ребята не умеют, так что постоянно заказывают еду в разных службах доставки. Так же поступают и их многочисленные соседи-коллеги.

Вчера Костя заболел, так что сегодня он не работает, а весь день сидит на подоконнике и грустно смотрит на улицу. Чтобы как-то занять себя, он следит за тем, какие доставщики еды подъезжают к его дому. За день к дому подъехало $$$n$$$ доставщиков, про каждого из которых Костя записал его компанию $$$a_i$$$ (им он присвоил номера от 1 до $$$10^9$$$).

Так как Костя — исследователь, он не может дать пропасть этому массиву данных. Для этого он хочет извлечь из него какую-нибудь полезную (или не очень) информацию. Например, какими службами доставки пользуются все его коллеги. Костя собирается выяснить это следующим образом: для каждого своего сослуживца он знает период его бодрствования, так что может выяснить, каких доставщиков он (чисто гипотетически) мог вызывать. Для $$$j$$$-го коллеги это были доставщики с $$$l_j$$$-го по $$$r_j$$$-го. Тогда для каждого коллеги Костя может определить самую вероятную службу доставки — ту, курьеров которой было больше всего в период его бодрствования.

Во время болезни Косте нельзя пользоваться ноутбуком, поэтому он просит вас закончить его исследование: для каждого живущего в доме сотрудника Яндекса определить самую вероятную для него службу доставки.

Входные данные

В первой строке дано одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — число доставшиков, увиденных Костей за день.

Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — номера службы доставки $$$i$$$-го доставщика.

В третьей строке дано одно целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество коллег Кости.

В следующих $$$q$$$ строках дано по два целых числа $$$l_j, r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — отрезок доставщиков, попадающих в период бодрствования $$$j$$$-го коллеги Кости.

Выходные данные

Выведите $$$q$$$ целых чисел — для каждого яндексоида номер самой вероятной для него службы доставки. Если ответов несколько, выведите любой.

Система оценки

$$$$$$\begin{array}{|c|c|c|c|c|} \hline \text { Подзадача } & \text { Баллы } & \text { Ограничения } & \text { Оценка } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text { подзадача } & \\ \hline 1 & 13 & n, q \le 100, a_i \le 100 & \text { подзадача } & \\ \hline 2 & 24 & n, q \le 10\,000, a_i \le 100 & \text { подзадача } & 1 \\ \hline 3 & 21 & n, q \le 10\,000, a_i \le 10\,000 & \text { подзадача } & 1, 2 \\ \hline 4 & 42 & \text{ Без дополнительных ограничений } & { потестовая } & 1, 2, 3 \\ \hline \end{array}$$$$$$

ПримерВходные данные

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

Выходные данные

2
2
4