Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Unmerge

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLet $$$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<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>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)$$$.

Input

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$$$.

Output

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".

Example

Input

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

Output

YES NO YES YES NO NO

Note

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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/21/2021 14:16:52 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|