小红的排列构造
题号:NC272304
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

小红拿到了一个长度为n的数组a,她希望你构造两个排列pq,满足对于i∈[1,n],a_ip_iq_i二选一。你能帮帮她吗?

定义排列是一个长度为n的数组,其中1到n每个元素恰好出现1次。

输入描述:

第一行输入一个正整数n,代表两个数组的长度。
第二行输入n个正整数a_i
1\leq n \leq 10^5
1\leq a_i \leq n

输出描述:

如果无解,请输出-1。
否则第一行输出n个正整数p_i,第二行输出n个正整数q_i,代表小红构造的两个排列。有多解时输出任意即可。
示例1

输入

复制
3
2 3 2

输出

复制
2 3 1
1 3 2
示例2

输入

复制
4
1 1 1 1

输出

复制
-1