Dada una secuencia $A_1, A_2, \ldots, A_N$ de longitud $N$. Escriba un programa que ejecute las siguientes consultas:

• i j: imprime la cantidad de ocurrencias del número más frecuente entre $A_i, A_{i+1}, \ldots, A_j$.

Entrada

La primera línea contiene la longitud $N$ de la secuencia $(1 \le N \le 100{,}000)$.

La segunda línea contiene $A_1, A_2, \ldots, A_N$ $(1 \le A_i \le 100{,}000)$.

La tercera línea contiene la cantidad $M$ de consultas $(1 \le M \le 100{,}000)$.

Las siguientes $M$ líneas contienen cada una una consulta $i, j$ $(1 \le i \le j \le n)$.

Salida

Para cada consulta, imprime una línea que contenga la respuesta.

Ejemplos

Entrada de ejemplo 1

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

Salida de ejemplo 1

2
1
2