CF1381B.Unmerge

Let $a$ and $b$ be two arrays of lengths $n$ and $m$, respectively, with no elements in common. We can define a new array $\mathrm{merge}(a,b)$ of length $n+m$ recursively as follows:

• If one of the arrays is empty, the result is the other array. That is, $\mathrm{merge}(\emptyset,b)=b$ and $\mathrm{merge}(a,\emptyset)=a$. In particular, $\mathrm{merge}(\emptyset,\emptyset)=\emptyset$.
• If both arrays are non-empty, and $a_1 \lt b_1$, then $\mathrm{merge}(a,b)=[a_1]+\mathrm{merge}([a_2,\ldots,a_n],b)$. That is, we delete the first element $a_1$ of $a$, merge the remaining arrays, then add $a_1$ to the beginning of the result.
• If both arrays are non-empty, and $a_1 \gt b_1$, then $\mathrm{merge}(a,b)=[b_1]+\mathrm{merge}(a,[b_2,\ldots,b_m])$. That is, we delete the first element $b_1$ of $b$, merge the remaining arrays, then add $b_1$ to the beginning of the result.

This algorithm has the nice property that if $a$ and $b$ are sorted, then $\mathrm{merge}(a,b)$ will also be sorted. For example, it is used as a subroutine in merge-sort. For this problem, however, we will consider the same procedure acting on non-sorted arrays as well. For example, if $a=[3,1]$ and $b=[2,4]$, then $\mathrm{merge}(a,b)=[2,3,1,4]$.

A permutation 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).

There is a permutation $p$ of length $2n$. Determine if there exist two arrays $a$ and $b$, each of length $n$ and with no elements in common, so that $p=\mathrm{merge}(a,b)$.

设 $a$ 和 $b$ 分别为长度为 $n$ 和 $m$ 的两个数组，且二者没有公共元素。我们可以递归地定义一个长度为 $n+m$ 的新数组 $\mathrm{merge}(a,b)$ 如下：

• 若其中一个数组为空，则结果为另一个数组。即，$\mathrm{merge}(\emptyset,b)=b$ 且 $\mathrm{merge}(a,\emptyset)=a$。特别地，$\mathrm{merge}(\emptyset,\emptyset)=\emptyset$。
• 若两个数组均非空，且 $a_1 \lt b_1$，则 $\mathrm{merge}(a,b)=[a_1]+\mathrm{merge}([a_2,\ldots,a_n],b)$。即：删除 $a$ 的首元素 $a_1$，对剩余数组进行合并，再将 $a_1$ 添加到结果的开头。
• 若两个数组均非空，且 $a_1 \gt b_1$，则 $\mathrm{merge}(a,b)=[b_1]+\mathrm{merge}(a,[b_2,\ldots,b_m])$。即：删除 $b$ 的首元素 $b_1$，对剩余数组进行合并，再将 $b_1$ 添加到结果的开头。

该算法具有如下良好性质：若 $a$ 和 $b$ 均为升序排列，则 $\mathrm{merge}(a,b)$ 也必为升序排列。例如，它被用作归并排序（merge-sort）中的子程序。然而，本题中我们将同样考虑该过程作用于非升序排列的数组的情形。例如，若 $a=[3,1]$ 且 $b=[2,4]$，则 $\mathrm{merge}(a,b)=[2,3,1,4]$。

一个排列（permutation）是指由 $1$ 到 $n$ 这 $n$ 个互不相同的整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列；但 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中却出现了 $4$）。

现给定一个长度为 $2n$ 的排列 $p$。请判断是否存在两个长度均为 $n$、且彼此无公共元素的数组 $a$ 和 $b$，使得 $p=\mathrm{merge}(a,b)$。

The first line contains a single integer $t$ ($1\le t\le 1000$) — the number of test cases. Next $2t$ lines contain descriptions of test cases.

The first line of each test case contains a single integer $n$ ($1\le n\le 2000$).

The second line of each test case contains $2n$ integers $p_1,\ldots,p_{2n}$ ($1\le p_i\le 2n$). It is guaranteed that $p$ is a permutation.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2000$.

第一行包含一个整数 $t$（$1\le t\le 1000$）—— 表示测试用例的数量。接下来的 $2t$ 行包含各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\le n\le 2000$）。

每个测试用例的第二行包含 $2n$ 个整数 $p_1,\ldots,p_{2n}$（$1\le p_i\le 2n$）。保证 $p$ 是一个排列。

保证所有测试用例中 $n$ 的总和不超过 $2000$。

For each test case, output "YES" if there exist arrays $a$, $b$, each of length $n$ and with no common elements, so that $p=\mathrm{merge}(a,b)$. Otherwise, output "NO".

对于每个测试用例，如果存在两个长度均为 $n$ 且无公共元素的数组 $a$ 和 $b$，使得 $p=\mathrm{merge}(a,b)$，则输出 "YES"；否则输出 "NO"。

In the first test case, $[2,3,1,4]=\mathrm{merge}([3,1],[2,4])$.

In the second test case, we can show that $[3,1,2,4]$ is not the merge of two arrays of length $2$.

In the third test case, $[3,2,6,1,5,7,8,4]=\mathrm{merge}([3,2,8,4],[6,1,5,7])$.

In the fourth test case, $[1,2,3,4,5,6]=\mathrm{merge}([1,3,6],[2,4,5])$, for example.

在第一个测试用例中，$[2,3,1,4]=\mathrm{merge}([3,1],[2,4])$。

在第二个测试用例中，我们可以证明 $[3,1,2,4]$ 不是两个长度均为 $2$ 的数组的合并结果。

在第三个测试用例中，$[3,2,6,1,5,7,8,4]=\mathrm{merge}([3,2,8,4],[6,1,5,7])$。

在第四个测试用例中，例如 $[1,2,3,4,5,6]=\mathrm{merge}([1,3,6],[2,4,5])$。