Nasser y el arreglo igual#13082

Nasser y el arreglo igual

1 segundo

256 megabytes

Nasser tiene un arreglo $a$ de $n$ enteros positivos. Puede realizar las siguientes operaciones cualquier número de veces (posiblemente cero), en cualquier orden:

1. Elegir un índice $i$ ( $1 \leq i \leq n$ 1 \le i \le n) e incrementar $a_{i}$ a_i en $2$ .

2. Elegir un segmento $[l, r]$ [l, r] ( $1 \leq l < r \leq n$ 1 \le l < r \le n) tal que $a_{l} = a_{l + 1} = \dots = a_{r}$ a_l = a_{l+1} = \ldots = a_r, e incrementar en $1$ cada uno de $a_{l}, a_{l + 1}, \dots, a_{r}$ a_l, a_{l+1}, \ldots, a_r.

Observe que la segunda operación requiere que el segmento elegido contenga al menos dos elementos, todos ellos iguales en el momento de realizar la operación. Por ejemplo, si $a = [4, 5, 5, 7]$ a = [4, 5, 5, 7], se puede elegir el segmento $[2, 3]$ , pero no se pueden elegir los segmentos $[1, 2]$ ni $[2, 4]$ .

Determine si Nasser puede lograr que todos los elementos del arreglo sean iguales.

Entrada

Cada test contiene múltiples casos de prueba. La primera línea contiene un único entero $t$ $(1 \leq t \leq 1 0^{4})$ (1 \le t \le 10^4) — el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene un único entero $n$ $(1 \leq n \leq 2 \cdot 1 0^{5})$ (1 \le n \le 2 \cdot 10^5) — el tamaño del arreglo.

La segunda línea de cada caso de prueba contiene $n$ enteros $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n $(1 \leq a_{i} \leq 1 0^{9})$ (1 \le a_i \le 10^9) — los elementos del arreglo.

Se garantiza que la suma de $n$ sobre todos los casos de prueba no excede $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Salida

Imprima YES si es posible hacer que todos los elementos sean iguales usando las operaciones permitidas. En caso contrario, imprima NO.

Puede imprimir la respuesta usando cualquier combinación de mayúsculas y minúsculas. Por ejemplo, las cadenas yEs, yes, Yes y YES serán aceptadas como respuestas afirmativas válidas.

Ejemplos

Ejemplo 1

Nota

En el primer caso de prueba, $a = [1, 2]$ a = [1, 2]. La diferencia $a_{2} - a_{1}$ a_2 - a_1 es igual a $1$ . La primera operación cambia esta diferencia exactamente en $2$ , por lo que siempre permanece impar y nunca llega a ser $0$ . La segunda operación solo puede aplicarse a dos elementos adyacentes iguales, así que aquí nunca puede aplicarse. Por lo tanto, los elementos nunca podrán ser iguales.

En el segundo caso de prueba, $a = [2, 4]$ a = [2, 4]. Aplique la primera operación con $i = 1$ i = 1: $[2, 4] \to [4, 4]$ [2, 4] \to [4, 4].

En el cuarto caso de prueba, $a = [3, 2, 2, 1]$ a = [3, 2, 2, 1]. Aplique la segunda operación con $[l, r] = [2, 3]$ [l, r] = [2, 3]: $[3, 2, 2, 1] \to [3, 3, 3, 1]$ [3, 2, 2, 1] \to [3, 3, 3, 1]. Luego aplique la primera operación con $i = 4$ i = 4: $[3, 3, 3, 1] \to [3, 3, 3, 3]$ [3, 3, 3, 1] \to [3, 3, 3, 3].

Puntuación

Subtarea $1$ ( $100$ puntos) : Sin restricciones adicionales.