Permutaciones
10 soluciones
500 puntos
Herald tiene una matriz dimensional que consta de N enteros. En un segundo Herald puede intercambiar dos elementos de la matriz que sean vecinos. Ahora Herald se pregunta si puede obtener una matriz en la que el elemento vecino de cualquier entero de la matriz sea distinto en un tiempo finito. ¿Cómo hacerlo? Ayuda a Herald a saber la respuesta.
Input
La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 <= M <= 100)
Cada caso está compuesto de la(s) siguiente(s) linea(s):
N : La primera línea de cada caso contiene un entero que indica el número de elementos en el arreglo. (1 ≤ N ≤ 100)
La segunda línea contiene N enteros donde a1, a2, ..., ai (1 ≤ ai ≤ 1000) corresponden a los elementos del conjunto.
Output
Para cada caso debes responder una única línea con la palabra "YES" (sin las comillas) si Herald puede obtener el conjunto que necesita, y "NO" (sin las comillas) en caso contrario.
Entrada de ejemplo
Input |
3 |
Output |
YES |
Nota
En el primer caso la matriz inicial queda igual.
En el segundo caso Herald puede obtener un array: 1, 2, 1. Cambiando el último y el penúltimo elemento para obtenerlo.
En el tercer caso Herald no puede obtener la variedad que necesita.
