CF1906E.Merge Not Sort

You are currently researching the Merge Sort algorithm. Merge Sort is a sorting algorithm that is based on the principle of Divide and Conquer. It works by dividing an array into two subarrays of equal length, sorting each subarrays, then merging the sorted subarrays back together to form the final sorted array.

You are particularly interested in the merging routine. Common merge implementation will combine two subarrays by iteratively comparing their first elements, and move the smaller one to a new merged array. More precisely, the merge algorithm can be presented by the following pseudocode.

Merge(A[1..N], B[1..N]):
C = []
i = 1
j = 1
while i <= N AND j <= N:
if A[i] < B[j]:
append A[i] to C
i = i + 1
else:
append B[j] to C
j = j + 1
while i <= N:
append A[i] to C
i = i + 1
while j <= N:
append B[j] to C
j = j + 1
return C

During your research, you are keen to understand the behaviour of the merge algorithm when arrays $A$ and $B$ are not necessarily sorted. For example, if $A = [3, 1, 6]$ and $B = [4, 5, 2]$, then $\text{Merge}(A, B) = [3, 1, 4, 5, 2, 6]$.

To further increase the understanding of the merge algorithm, you decided to work on the following problem. You are given an array $C$ of length $2 \cdot N$ such that it is a permutation of $1$ to $2 \cdot N$. Construct any two arrays $A$ and $B$ of the same length $N$, such that $\text{Merge}(A, B) = C$, or determine if it is impossible to do so.

你目前正在研究归并排序（Merge Sort）算法。归并排序是一种基于“分治”（Divide and Conquer）思想的排序算法。其工作原理是：将一个数组划分为两个长度相等的子数组，分别对这两个子数组进行排序，再将已排序的子数组合并成最终的有序数组。

你尤其关注其中的合并（merge）过程。常见的合并实现方式是：通过迭代比较两个子数组的首元素，将较小者移入一个新的合并数组中。更精确地，该合并算法可用如下伪代码描述：

Merge(A[1..N], B[1..N]):
C = []
i = 1
j = 1
while i <= N AND j <= N:
if A[i] < B[j]:
append A[i] to C
i = i + 1
else:
append B[j] to C
j = j + 1
while i <= N:
append A[i] to C
i = i + 1
while j <= N:
append B[j] to C
j = j + 1
return C

在研究过程中，你特别希望理解当数组 $A$ 和 $B$ 不一定有序时，该合并算法的行为。例如，若 $A = [3, 1, 6]$ 且 $B = [4, 5, 2]$，则 $\text{Merge}(A, B) = [3, 1, 4, 5, 2, 6]$。

为进一步加深对合并算法的理解，你决定研究如下问题：给定一个长度为 $2 \cdot N$ 的数组 $C$，且 $C$ 是 $1$ 到 $2 \cdot N$ 的一个排列。请构造任意两个长度均为 $N$ 的数组 $A$ 和 $B$，使得 $\text{Merge}(A, B) = C$；若不存在这样的 $A$ 和 $B$，则判定其不可能。

The first line consists of an integer $N$ ($1 \leq N \leq 1000$).

The following line consists of $2 \cdot N$ integers $C_i$. The array $C$ is a permutation of $1$ to $2 \cdot N$.

第一行包含一个整数 $N$（$1 \leq N \leq 1000$）。

接下来的一行包含 $2 \cdot N$ 个整数 $C_i$。数组 $C$ 是 $1$ 到 $2 \cdot N$ 的一个排列。

If it is impossible to construct two arrays $A$ and $B$ of length $N$ such that $\text{Merge}(A, B) = C$, then output -1.

Otherwise, output the arrays $A$ and $B$ in two lines. The first line consists of $N$ integers $A_i$. The second line consists of $N$ integers $B_i$. If there are several possible answers, output any of them.

如果无法构造两个长度为 $N$ 的数组 $A$ 和 $B$，使得 $\text{Merge}(A, B) = C$，则输出 -1。

否则，在两行中分别输出数组 $A$ 和 $B$。第一行包含 $N$ 个整数 $A_i$，第二行包含 $N$ 个整数 $B_i$。若存在多种可能的答案，输出任意一种即可。

Explanation for the sample input/output #1

The solution $A = [3, 1, 4]$ and $B = [5, 2, 6]$ is also correct.

Explanation for the sample input/output #2

The solution $A = [1, 2, 3, 4]$ and $B = [5, 6, 7, 8]$ is also correct.

样例输入/输出 #1 的说明

解 $A = [3, 1, 4]$ 和 $B = [5, 2, 6]$ 同样正确。

样例输入/输出 #2 的说明

解 $A = [1, 2, 3, 4]$ 和 $B = [5, 6, 7, 8]$ 同样正确。