J. Pseudo Merge Sort
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For any two integer arrays $$$a$$$ and $$$b$$$ of lengths $$$n$$$ and $$$m$$$, each containing distinct elements and there are no common elements between them, define $$$f(a,b)$$$ as follows:

$$$$$$ f(a,b) = \begin{cases} \emptyset & a = \emptyset \land b = \emptyset \\ a & b = \emptyset \\ b & a = \emptyset \\ [a_1]+f([a_2,a_3,\ldots,a_n],b) & a_1 \lt b_1 \\ [b_1]+f(a,[b_2,b_3,\ldots,b_m]) & a_1 \gt b_1 \end{cases} $$$$$$

where $$$+$$$ is defined as the concatenation of two arrays.

You are now given a permutation $$$p$$$ of length $$$2n$$$. You need to determine whether it is possible to find two arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$ and together containing all integers from $$$1$$$ to $$$2n$$$ exactly once, such that $$$f(a,b)=p$$$.

A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — half the length of $$$p$$$.

The second line contains $$$2n$$$ integers $$$p_1,p_2,\ldots,p_{2n}$$$ ($$$1 \le p_i \le 2n$$$) — the permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, if there exist $$$a$$$, $$$b$$$ satisfying the constraints, output YES; otherwise, output NO. 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.

Example
Input
3
2
2 3 1 4
2
3 1 2 4
4
3 2 6 1 5 7 8 4
Output
YES
NO
YES