Dada una lista de números, que contiene los números ~1, 2, \dots, n~ en algún orden.

Determine si es posible ordenar la lista de menor a mayor, realizando la siguiente operación cualquier número de veces (es posible no realizar ninguna operación):

• Seleccionar dos enteros ~i, j~ tal que ~1 < i+1 < j < n~, intercambiar los valores en las posiciones ~i~ y ~j~, e intercambiar los valores en las posiciones ~i+1~ y ~j+1~.

Por ejemplo, la lista ~[2, 3, 5, 1, 4]~ puede ser ordenada usando dos operaciones:

1. Seleccionar ~i=1~ y ~j=4~, la nueva lista obtenida luego de intercambiar los valores sería ~[1, 4, 5, 2, 3]~.
2. Seleccionar ~i=2~ y ~j=4~, la nueva lista obtenida luego de intercambiar los valores sería ~[1, 2, 3, 4, 5]~.

Subtareas

• Subtarea 1 (22 puntos): ~1 \le t \le 1000~, ~1 \le n \le 8~.
• Subtarea 2 (34 puntos): ~1 \le t \le 1000~, ~1 \le n \le 100~.
• Subtarea 3 (44 puntos): ~1 \le t \le 1000~, ~1 \le n \le 10000~.

Entrada

La primera línea contiene un entero ~t~: el número de casos de prueba.

Le siguen ~2*n~ líneas que describen cada caso de prueba. La primera línea de cada caso de prueba contiene un entero ~n~ y la segunda describe el contenido de la lista.

Salida

Por cada caso imprime "YES" si la lista puede ser ordenada, de lo contrario imprime "NO".

Ejemplos

Entrada 1

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

Salida 1

YES
YES
NO