Реалізуйте sqrt-декомпозицію запитів (алгоритм Мо) для знаходження моди на відрізку.
Мода - в статистиці, елемент який зустрічається найбільшу кількість раз. Якщо таких елементів декілька, виведіть найбільший з них.

Формат вхідних даних

В першому рядку ціле число \(N\), кількість елементів масиву (\(1 \le N \le 50000\)).
В другому рядку елементи масиву. (\(1 \le Ai \le 10^5\))
В третьому рядку вводиться число \(K\) - кількість запитів (\(1 \le K \le 30000\))
В кожному з наступних \(K\) рядків міститься по два числа - номера лівого і правого елементів відрізка масиву

Формат вихідних даних

Для кожного запиту виведіть через пробіл - відповідь на запит

Приклад вхідних даних

5
2 2 2 1 5
2
2 3
2 5

Приклад вихідних даних

2 2