Good Sequence Partition

Given an even-length sequence \(a_1, a_2, \dots, a_n\), we call it a good sequence if and only if there exists a partition of the sequence into two subsequences

[ U = {a_{i_1}, a_{i_2}, \dots, a_{i_{n/2}}} \quad \text{and} \quad V = {a_{j_1}, a_{j_2}, \dots, a_{j_{n/2}}}, \quad \text{where} \quad {a_1, a_2, \dots, a_n} = U \cup V, ]

such that if we let the indices satisfy:

[ i_1 < i_2 < \dots < i_{n/2} \quad \text{and} \quad j_1 < j_2 < \dots < j_{n/2}, ]

then the corresponding subsequences are strictly increasing in value:

[ a_{i_1} < a_{i_2} < \dots < a_{i_{n/2}}, \quad \text{and} \quad a_{j_1} < a_{j_2} < \dots < a_{j_{n/2}}. ]

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

Your task is to determine whether each given sequence is a good sequence.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each test case is described as follows:

• The first line contains an even integer \(n\) (\(2 \le n \le\) some limit) representing the length of the sequence.
• The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\).

It is guaranteed that \(n\) is even.

outputFormat

For each test case, output a single line containing YES if the sequence is good, and NO otherwise.

sample

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

YES
NO