Problem description

Dana jest tablica liczb M.

Dla danych przedziałów w tej tablicy znajdź najczęściej występującą w nich liczbę.

Wejście

Pierwsza linia wejścia zawiera liczbę n – liczbę elementów tablicy. W kolejnej linii dane jest n liczb x_i – kolejne elementy tablicy (której indeksy zaczynają się od 1 do n).

W następnym wierszu dana jest liczba q – liczba zapytań. W kolejnych q wierszach dane są po dwie liczby a i b – odpowiednio początek i koniec przedziału.

Wyjście

Dla każdego zapytania wypisz w osobnym wierszu odpowiedź – najczęściej występującą liczbę na tym przedziale. Jeżeli takich liczb jest kilka, wypisz najmniejszą z nich.

Ograniczenia

1 ≤ n ≤ 10 000, 1 ≤ q ≤ 10 000, 1 ≤ a ≤ b ≤ n,  − 10⁹ ≤ x_i ≤ 10⁹

Przykład

8
1 2 3 5 5 7777 2 2
4
1 1
4 6
6 8
1 8

1
5
2
2