5315. Пицца для вечеринок

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

У Кодеруна есть список из $n$ заказов на пиццу. Кодерун следит за тем, чтобы друзей на доставке не перегружали заказы. Для каждого заказа он знает номер друга, доставлявшего заказ. Для проверки он $m$ раз выбирает какой-то отрезок из заказов и убеждается, что на нём нет друга, доставившего больше половины заказов.

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

Первая строка входных данных содержит два целых числа $n$ и $m$ ($1 \leq n, m \leq 5 \cdot 10^5$) — количество заказов и количество отрезков, которые проверяет Кодерун, соответственно.

Вторая строка содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$) — номер друга, который доставлял $i$-й заказ.

Далее следуют $m$ строк запросов. $j$-я из следующих $m$ строк содержит два целых числа $l_j$ и $r_j$ ($1 \leq l_j \leq r_j \leq n$) — описание $j$-го запроса.

Для каждого запроса выведите одно целое число — номер друга, который доставил больше половины заказов на отрезке или $0$, если такого друга нет.