B. Разъединение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$a$$$ и $$$b$$$ это два массива, имеющих длины $$$n$$$ и $$$m$$$, соответственно, такие что ни один элемент первого массива не равен ни одному элементу второго массива. Мы можем определить новый массив $$$\mathrm{merge}(a,b)$$$ длины $$$n+m$$$ по следующему рекурсивному правилу:

  • Если один из массивов пустой, результат равен другому массиву. То есть, $$$\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_1$$$ из $$$a$$$, объединяем новые массивы, затем добавляем $$$a_1$$$ в начало результата.
  • Если оба массива непустые и $$$a_1>b_1$$$, тогда $$$\mathrm{merge}(a,b)=[b_1]+\mathrm{merge}(a,[b_2,\ldots,b_m])$$$. То есть мы удаляем первый элемент $$$b_1$$$ из $$$b$$$, объединяем новые массивы, затем добавляем $$$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$$$ встречается в массиве).

У вас есть перестановка $$$p$$$ длины $$$2n$$$. Определите, существуют ли два массива $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если существуют массивы $$$a$$$, $$$b$$$, каждый длины $$$n$$$, которые не имеют общих элементов, такие что $$$p=\mathrm{merge}(a,b)$$$. Иначе выведите «NO».

Пример
Входные данные
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
Выходные данные
YES
NO
YES
YES
NO
NO
Примечание

В первом наборе входных данных $$$[2,3,1,4]=\mathrm{merge}([3,1],[2,4])$$$.

Во втором наборе входных данных можно показать, что $$$[3,1,2,4]$$$ не является результатом функции merge для двух массивов длины $$$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])$$$.