310896: CF1906E. Merge Not Sort

E. Merge Not Sorttime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output

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.

ExamplesInput

3
3 1 4 5 2 6

Output

3 1 6
4 5 2

Input

4
1 2 3 4 5 6 7 8

Output

2 3 5 7
1 4 6 8

Input

2
4 3 2 1

Output

-1

Note

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.

题目大意：
你正在研究归并排序算法中的归并部分。归并排序基于分治原则，通过将数组分成两个等长的子数组，分别排序后再合并。你特别关注归并的细节，即如何合并两个子数组。给定的伪代码展示了这一过程。

现在，你想了解当两个数组A和B不一定有序时，归并算法的行为。例如，如果A=[3,1,6]，B=[4,5,2]，则Merge(A,B)=[3,1,4,5,2,6]。

为了进一步理解归并算法，你决定解决以下问题：给定一个长度为2*N的数组C，它是1到2*N的排列。构造任意两个长度相同的数组A和B，使得Merge(A,B)=C，或者确定这是不可能的。

输入输出数据格式：
输入：
- 第一行包含一个整数N（1≤N≤1000）。
- 下一行包含2*N个整数Ci，数组C是1到2*N的排列。

输出：
- 如果无法构造长度为N的数组A和B使得Merge(A,B)=C，则输出-1。
- 否则，输出数组A和B，每行N个整数。如果有多个可能的答案，输出其中任何一个。

示例：
输入：
3
3 1 4 5 2 6
输出：
3 1 6
4 5 2

输入：
4
1 2 3 4 5 6 7 8
输出：
2 3 5 7
1 4 6 8

输入：
2
4 3 2 1
输出：
-1

注意：
对于示例输入/输出#1，解A=[3,1,4]和B=[5,2,6]也是正确的。
对于示例输入/输出#2，解A=[1,2,3,4]和B=[5,6,7,8]也是正确的。题目大意： 你正在研究归并排序算法中的归并部分。归并排序基于分治原则，通过将数组分成两个等长的子数组，分别排序后再合并。你特别关注归并的细节，即如何合并两个子数组。给定的伪代码展示了这一过程。 现在，你想了解当两个数组A和B不一定有序时，归并算法的行为。例如，如果A=[3,1,6]，B=[4,5,2]，则Merge(A,B)=[3,1,4,5,2,6]。 为了进一步理解归并算法，你决定解决以下问题：给定一个长度为2*N的数组C，它是1到2*N的排列。构造任意两个长度相同的数组A和B，使得Merge(A,B)=C，或者确定这是不可能的。 输入输出数据格式： 输入： - 第一行包含一个整数N（1≤N≤1000）。 - 下一行包含2*N个整数Ci，数组C是1到2*N的排列。 输出： - 如果无法构造长度为N的数组A和B使得Merge(A,B)=C，则输出-1。 - 否则，输出数组A和B，每行N个整数。如果有多个可能的答案，输出其中任何一个。 示例： 输入： 3 3 1 4 5 2 6 输出： 3 1 6 4 5 2 输入： 4 1 2 3 4 5 6 7 8 输出： 2 3 5 7 1 4 6 8 输入： 2 4 3 2 1 输出： -1 注意： 对于示例输入/输出#1，解A=[3,1,4]和B=[5,2,6]也是正确的。 对于示例输入/输出#2，解A=[1,2,3,4]和B=[5,6,7,8]也是正确的。