CSES - Datatähti Open 2021 - Sorting
  • Time limit: 1.00 s
  • Memory limit: 512 MB
You are given a list of numbers, which contains the numbers $1,2,\dots,n$ in some order.

Determine whether it is possible to sort the numbers from smallest to largest by repeating the following operation zero or more times: choose two separate pairs of adjacent numbers, and switch these pairs with each other.

For example, the list $[2,3,5,1,4]$ can be sorted using two operations: $[\underline{2,3},5,\underline{1,4}] \rightarrow [1,\underline{4,5},\underline{2,3}] \rightarrow [1,2,3,4,5]$.

Input

The first line of input consists of an integer $t$: the number of test cases.

The first line of each test contains the integer $n$ and the second line describes the contents of the list.

Output

For each test, print YES if the list can be sorted, NO otherwise.

Example

Input:
3
2
1 2
5
2 3 5 1 4
4
1 2 4 3


Output:
YES
YES
NO


Subtask 1 (36 points)
  • $1 \le t \le 1000$
  • $1 \le n \le 8$
Subtask 2 (64 points)
  • $1 \le t \le 1000$
  • $1 \le n \le 100$