Frondy se encuentra muy feliz pasando su servicio militar activo en el Ejército Oriental. Por su buen comportamiento fue asignado al almacén de municiones de su unidad como especialista en municiones y explosivos. El almacén puede ser modelado como un arreglo a de tamaño n, donde ai representa el tipo de munición en la ~i~-ésima posición.

Como parte de su trabajo, Frondy debe identificar posibles riesgos de explosión. Se dice que un rango ~[l,r]~ es peligroso si existe algún tipo de munición ~p~ que represente más del ~50%~ de dicho rango. Formalmente, si ~f(l,r,p)~ denota la cantidad de veces que aparece ~p~ entre ~l~ y ~r~, entonces el rango es peligroso si:

~f(l,r,p) > \lfloor \frac{r-l+1}{2} \rfloor~

Frondy necesita revisar varios rangos para saber cuales son peligrosos y cuales no y así poder aplicar el protocolo de seguridad así que Frondy le pide ayuda a usted para que lo ayudes a computar ~q~ consultas, en cada una debe evaluar un rango ~[l,r]~ y responder si es o no peligroso.

Entrada

La primera línea de entrada contiene un entero ~n~ (~1 \le n \le 2 \cdot 10^5~) que representa el tamaño del almacén (el arreglo).

La segunda línea constará de ~n~ enteros ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~) los cuales representan el tipo de munición en su respectiva posición del arreglo.

La tercera línea contiene un entero ~q~ (~1 \le q \le 2 \cdot 10^5~), seguido por ~q~ consultas de la forma ~l_i~ ~r_i~ (~1 \le l_i \le r_i \le n~).

Salida

Deberá responder por cada una de las ~q~ consultas con YES si el rango que representa la consulta es peligroso, o NO en caso contrario.

Puntuación

Subtarea	Condiciones	Puntos	Dependencias
~1~	~1 \le n \le 100~, ~1 \le a_i \le 10^5~	~8~	~-~
~2~	~1 \le n \le 5 \cdot 10^3~	~20~	~1~
~3~	~1 \le a_i \le 10~	~7~	~-~
~4~	~1 \le n, q \le 5 \cdot 10^4~	~35~	~1,2~
~5~	~-~	~30~	~3,4~

Ejemplos

Entrada de ejemplo 1

3
6 4 5
2
2 3
3 3

Salida de ejemplo 1

NO
YES

Entrada de ejemplo 2

5
7 6 4 5 4
15
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5

Entrada de ejemplo 2

YES
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
YES
YES
NO
YES