Two players, Souvlaki and Kalamaki, are given a sequence $a$ of $n$ integers.

They will play a game that consists of $n-1$ rounds, which are numbered from $1$ to $n-1$. Souvlaki plays on odd-numbered rounds, and Kalamaki on even-numbered rounds.

On the $i$-th round, a player can choose to take exactly one of the following actions:

• Skip his turn and proceed to round $i+1$ (or finish the game if round $i$ was the last one).
• Swap elements $a_i$ and $a_{i+1}$.

Souvlaki wins if after the end of the last round, $a$ is sorted in non-decreasing order. In other words, he wins if $a_i \le a_{i+1}$ holds for every $1 \le i \lt n$. Otherwise, Kalamaki wins.

However, Souvlaki does not like losing, so before the start of the game, he may re-order the elements of $a$ in anyway he wants. Is it possible for him to do so such that he has a guaranteed winning strategy?

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows.

The first line of each test case contains a single integer, $n$ ($3 \le n \le 100$) — the number of integers in $a$.

The second line contains exactly $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — where $a_i$ represents the $i$-th element of $a$.

Output

For each test case, output on a separate line "'YES"' if it is possible for Souvlaki to re-order the elements of $a$ such that he has a guaranteed winning strategy, and "'NO"' otherwise.

You can output the answer in any case (upper or lower). For example, the strings "'yEs"', "'yes"', "'Yes"', and "'YES"' will be recognized as positive responses.

Note

In the first example, $a = [4, 2, 2, 1]$. A possible way to re-order the elements so that Souvlaki can win is the following: $a = [2, 1, 2, 4]$. Then, the game might go as follows:

1. On round $1$, it is Souvlaki's turn. He will choose to swap $a_1$ with $a_2$, and now $a = [1, 2, 2, 4]$.
2. On round $2$, it is Kalamaki's turn. Whether he chooses to skip his turn or swap elements $a_2$ and $a_3$, $a$ will remain the same. Suppose he skips his turn.
3. On round $3$, it is Souvlaki's turn. He can choose to skip his turn as well, because if he swapped the last two elements he would lose.

After every round, $a = [1, 2, 2, 4]$, sorted in non-decreasing order, so Souvlaki wins, no matter how Kalamaki chooses to play.

On the second example, since every element is equal, Souvlaki will always win because $a$ is always sorted in non-decreasing order.

Samples

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

YES
YES
YES
NO
NO