您目前正在研究归并排序算法。归并排序是一种基于分而治之原理的排序算法。它的工作原理是将数组分成两个长度相等的子数组,对每个子数组进行排序,然后将排序后的子数组合并在一起以形成最终的排序数组。
您对合并例程特别感兴趣。常见的合并实现将通过迭代比较两个子数组的第一个元素来合并两个子数组,并将较小的子数组移动到新的合并数组。更准确地说,合并算法可以由以下伪代码表示。
在您的研究过程中,您渴望了解当数组 $$$A$$$ 和 $$$B$$$ 不一定已排序时合并算法的行为。例如,如果 $$$A = [3, 1, 6]$$$ 且 $$$B = [4, 5, 2]$$$,则 $$$\text{Merge}(A, B) = [3, 1, 4, 5, 2, 6]$$$。
为了进一步加深对合并算法的理解,您决定解决以下问题。给定一个长度为 $$$2 \cdot N$$$ 的数组 $$$C$$$,它是 $$$1$$$ 到 $$$2 \cdot N$$$ 的排列。构造任意两个长度相同的数组$$$A$$$和$$$B$$$,使得$$$\text{Merge}(A, B) = C$$$,或者判断是否不可能这样做。
输入
第一行由整数 $$$N$$$ ($$$1 \leq N \leq 1000$$$) 组成。
下面一行由 $$$2 \cdot N$$$ 整数 $$$C_i$$$ 组成。数组 $$$C$$$ 是 $$$1$$$ 到 $$$2 \cdot N$$$ 的排列。
输出
如果无法构造长度为 $$$N$$$ 的两个数组 $$$A$$$ 和 $$$B$$$ 使得 $$$\text{Merge}(A, B) = C$$$,则输出 -1。
否则,分两行输出数组 $$$A$$$ 和 $$$B$$$。第一行由 $$$N$$$ 整数 $$$A_i$$$ 组成。第二行由$$$N$$$ 整数$$$B_i$$$ 组成。如果有多个可能的答案,则输出其中任何一个。
示例
输入 #1
3 3 1 4 5 2 6
输出 #1
3 1 6 4 5 2
输入 #2
4 1 2 3 4 5 6 7 8
输出 #2
2 3 5 7 1 4 6 8
输入 #3
2 4 3 2 1
输出 #3
-1
注意
示例输入/输出 #1 的说明
解 $$$A = [3, 1, 4]$$$ 和 $$$B = [5, 2, 6]$$$ 也是正确的。
示例输入/输出#2 的说明
解 $$$A = [1, 2, 3, 4]$$$ 和 $$$B = [5, 6, 7, 8]$$$ 也是正确的。