Задача . B. Разъединение

Пусть \(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)\).