Consider a sequence $a_1, a_2, \dots, a_n$ of even length $n$. We call this sequence "good" if and only if there exists a partition of $a_1, a_2, \dots, a_n$ into two sets $U=\{a_{i_1}, a_{i_2}, \dots, a_{i_{n/2}}\}$ and $V=\{a_{j_1}, a_{j_2}, \dots, a_{j_{n/2}}\}=\{a_1, a_2, \dots, a_n\} \setminus U$ such that $i_1 < i_2 < \dots < i_{n/2}$, $a_{i_1} < a_{i_2} < \dots < a_{i_{n/2}}$, $j_1 < j_2 < \dots < j_{n/2}$, and $a_{j_1} < a_{j_2} < \dots < a_{j_{n/2}}$.

For example, the sequence $3, 1, 4, 5, 8, 7$ is a good sequence because it can be partitioned into $U=\{3, 4, 8\}$ and $V=\{1, 5, 7\}$. However, the sequence $3, 2, 1, 6, 5, 4$ is not a good sequence.

Given several sequences, your task is to determine whether each of them is a good sequence.

Input

The first line contains a single integer $m$, representing the number of sequences to check. The next $m$ lines each provide one of these sequences. Each sequence is given on a single line, where the first number is an even integer $n$, representing the length of the sequence, followed by $n$ integers representing the elements of the sequence $a_1, a_2, \dots, a_n$. The numbers on each line are separated by spaces.

Output

Output $m$ lines. If the $i$-th sequence is a good sequence, output Yes! on the $i$-th line; otherwise, output No!.

Examples

Input 1

2
6 3 1 4 5 8 7
6 3 2 1 6 5 4

Output 1

Yes!
No!

Subtasks

• 10% of the data: $n \le 100$
• 40% of the data: $n \le 300$
• 100% of the data: $n \le 2000$
• 100% of the data: $m \le 25,\ 0 \le a_1, a_2, \dots, a_n \le 10^6$