{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eLet $$$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:\u003c/p\u003e\u003cul\u003e \u003cli\u003e If one of the arrays is empty, the result is the other array. That is, $$$\\mathrm{merge}(\\emptyset,b)\u003db$$$ and $$$\\mathrm{merge}(a,\\emptyset)\u003da$$$. In particular, $$$\\mathrm{merge}(\\emptyset,\\emptyset)\u003d\\emptyset$$$. \u003c/li\u003e\u003cli\u003e If both arrays are non-empty, and $$$a_1\u0026lt;b_1$$$, then $$$\\mathrm{merge}(a,b)\u003d[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. \u003c/li\u003e\u003cli\u003e If both arrays are non-empty, and $$$a_1\u0026gt;b_1$$$, then $$$\\mathrm{merge}(a,b)\u003d[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. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThis 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\u003d[3,1]$$$ and $$$b\u003d[2,4]$$$, then $$$\\mathrm{merge}(a,b)\u003d[2,3,1,4]$$$.\u003c/p\u003e\u003cp\u003eA 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\u003d3$$$ but there is $$$4$$$ in the array).\u003c/p\u003e\u003cp\u003eThere 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\u003d\\mathrm{merge}(a,b)$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a single integer $$$t$$$ ($$$1\\le t\\le 1000$$$) \u0026nbsp;— the number of test cases. Next $$$2t$$$ lines contain descriptions of test cases. \u003c/p\u003e\u003cp\u003eThe first line of each test case contains a single integer $$$n$$$ ($$$1\\le n\\le 2000$$$).\u003c/p\u003e\u003cp\u003eThe 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.\u003c/p\u003e\u003cp\u003eIt is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2000$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eYES\u003c/span\u003e\" if there exist arrays $$$a$$$, $$$b$$$, each of length $$$n$$$ and with no common elements, so that $$$p\u003d\\mathrm{merge}(a,b)$$$. Otherwise, output \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eNO\u003c/span\u003e\".\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6\n2\n2 3 1 4\n2\n3 1 2 4\n4\n3 2 6 1 5 7 8 4\n3\n1 2 3 4 5 6\n4\n6 1 3 7 4 5 8 2\n6\n4 3 2 5 1 11 9 12 8 6 10 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES\nNO\nYES\nYES\nNO\nNO\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first test case, $$$[2,3,1,4]\u003d\\mathrm{merge}([3,1],[2,4])$$$.\u003c/p\u003e\u003cp\u003eIn the second test case, we can show that $$$[3,1,2,4]$$$ is not the merge of two arrays of length $$$2$$$.\u003c/p\u003e\u003cp\u003eIn the third test case, $$$[3,2,6,1,5,7,8,4]\u003d\\mathrm{merge}([3,2,8,4],[6,1,5,7])$$$.\u003c/p\u003e\u003cp\u003eIn the fourth test case, $$$[1,2,3,4,5,6]\u003d\\mathrm{merge}([1,3,6],[2,4,5])$$$, for example.\u003c/p\u003e"}}]}