秽土转生解
题号:NC296359
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

解决完白绝后,小 Z 找到秽土转生的尼桑一起前往兜的大本营,准备解除秽土转生。
经过一番鏖战,兜被尼桑伊邪娜美硬控,于是尼桑准备让兜说出解秽土的印。
但是兜早有防备,竟然给了一个和正解相差不大的印。被尼桑发现后,小 Z 决定和他共同思考真正的印是什么。
形式化地,兜给了一个长度为 n 的排列 p,设 \text{inv(p)} 表示排列 p 的逆序对数,正确的排列 q 应该满足:
1. q \neq p
2. \text{inv(q) = inv(p)}
3. 在满足 1, 2 的条件下,q 的字典序尽量小。

现在他俩都被难住了,你能帮助他们和五影找到这个排列 q 吗?

为什么有五影呢?要知道,在 E, F 题中,五影实际上并没有参照你给的决策,所以现在快要被秽土斑劈了,因此五影也想解除秽土转生。
在几乎全部的情况下,PyPy 的运行速度优于 Python,我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。

输入描述:

第一行一个正整数 n \ (1 \leq n \leq 10^5),表示排列 p 的长度。
第二行 n 个不重不漏的正整数 \in [1, n],空格隔开,表示排列 p

输出描述:

如果存在这样的排列 q,输出一行 n 个不重不漏的正整数 \in [1, n],空格隔开,表示排列 q;否则输出 -1 表示无解。
示例1

输入

复制
4
4 1 3 2

输出

复制
2 4 3 1
示例2

输入

复制
3
1 2 3

输出

复制
-1

说明

除了 [1, 2, 3],不存在逆序对为 0 的排列。