I. Мода на отрезке

Для каждого запроса $(l, r)$ нужно назвать самое частое значение на отрезке, а при равенстве частот — наименьшее из таких значений.

Каркас — из классной задачи H: предподсчёт ответа для всех пар блоков и достройка двумя хвостами. Но там спрашивали только частоту, а здесь ещё и значение, и это добавляет одну трудность.

В первой строке $n$ и $q$ ($1 \le n, q \le 10^5$). Во второй строке $n$ чисел $a_i$ ($1 \le a_i \le 10^9$). В следующих $q$ строках по два числа $l$ и $r$ ($1 \le l \le r \le n$).

Для каждого запроса выведите самое частое значение на отрезке, а при равенстве частот — наименьшее из них.