D-小红的排列构造_牛客周赛 Round 145

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个长为 $n$ 的数组 $a$ ，保证 $n$ 为偶数。请构造两个长为 $n$ 的排列 $b,c$ ，使得：
$\hspace{23pt}\bullet$ 对于每个 $i\left(1 \leq i \leq n \right)$ ，都有 $a_i = b_i$ 或 $a_i = c_i$ 。
$\hspace{23pt}\bullet$ 至少有 $\tfrac{n}{2}$ 个 $i\left(1 \leq i \leq n \right)$ ，满足 $a_i = b_i$ 。
$\hspace{23pt}\bullet$ 至少有 $\tfrac{n}{2}$ 个 $i\left(1 \leq i \leq n \right)$ ，满足 $a_i = c_i$ 。
$\hspace{15pt}$ 请你构造两个合法的排列 $b,c$ ，或输出 $-1$ ，代表这不可能。

【名词解释】
$\hspace{15pt}$ 长度为 $n$ 的排列：由 $1,2,\dots,n$ 这 $n$ 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:

第一行输入一个整数 。
第二行输入  个整数 ，代表数组 。

输出描述:

如果不存在合法的两个排列，请输出 ；否则输出两行，每行  个整数，代表所构造的排列 。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1

输入

复制

8
7 6 7 3 1 1 4 5

输出

复制

7 6 5 3 1 8 2 4
6 2 7 3 8 1 4 5

示例2

输入

复制

6
1 1 4 5 1 4

输出

复制

-1