Dany jest ciąg $A_1, A_2, \ldots, A_N$ o długości $N$. Napisz program wykonujący następujące zapytania:

• i j: wypisz liczbę wystąpień najczęściej występującej liczby wśród $A_i, A_{i+1}, \ldots, A_j$.

Wejście

Pierwszy wiersz zawiera długość $N$ ciągu $(1 \le N \le 100\,000)$.

Drugi wiersz zawiera $A_1, A_2, \ldots, A_N$ $(1 \le A_i \le 100\,000)$.

Trzeci wiersz zawiera liczbę $M$ zapytań $(1 \le M \le 100\,000)$.

Kolejne $M$ wierszy zawiera po jednym zapytaniu $i, j$ $(1 \le i \le j \le n)$.

Wyjście

Dla każdego zapytania wypisz w osobnym wierszu odpowiedź.

Przykład

Przykładowe wejście 1

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

Przykładowe wyjście 1

2
1
2