设 $$$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<b_1$$$,则 $$$\mathrm{merge}(a,b)=[a_1]+\mathrm{merge}([a_2,\ldots,a_n],b)$$$。也就是说,我们删除 $$$a$$$ 的第一个元素 $$$a_1$$$,合并剩余的数组,然后将 $$$a_1$$$ 添加到结果的开头。
- 如果两个数组都非空,且 $$$a_1>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)$$$ 也会被排序。例如,它用作合并排序中的子例程。然而,对于这个问题,我们也将考虑作用于非排序数组的相同过程。例如,如果 $$$a=[3,1]$$$ 且 $$$b=[2,4]$$$,则 $$$\mathrm{merge}(a,b)=[2,3,1,4]$$$。
排列是一个数组,由 $$$n$$$ 不同的整数组成,从 $$$1$$$ 到 $$$n$$$ 以任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。
存在长度为 $$$2n$$$ 的排列 $$$p$$$。确定是否存在两个数组 $$$a$$$ 和 $$$b$$$,每个数组的长度为 $$$n$$$ 并且没有共同元素,因此 $$$p=\mathrm{merge}(a,b)$$$。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,如果存在数组$$$a$$$、$$$b$$$,每个长度为$$$n$$$并且没有公共元素,则输出“YES”,以便$$$p=\mathrm{merge}(a,b)$$$。否则,输出“NO”。
示例
输入 #1
6 2 2 3 1 4 2 3 1 2 4 4 3 2 6 1 5 7 8 4 3 1 2 3 4 5 6 4 6 1 3 7 4 5 8 2 6 4 3 2 5 1 11 9 12 8 6 10 7
输出 #1
YES NO YES YES NO NO
注意
在第一个测试用例中,$$$[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])$$$。