D-构造_牛客练习赛137

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

题目描述

$\mathbf{注意题目内排列的定义与常见的不同，值域在\ 0 \sim n - 1\ 范围}$

$\textbf{为了您的参赛体验，我们推荐: 当您不确定算法的正确性时，在正式提交此题之前测试所有样例}$

【排列】长度为 $n$ 的排列是由 $0 \sim n - 1$ 这 $n$ 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如， $\{1,2,0,4,3\}$ 是一个长度为 $5$

的排列，而 $\{0,1,1\}$ 和 $\{0,2,3\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

定义一个排列 $P$ 的前缀 $mex$ 序列为一个长度为 $n$ 的非负整数数组 $pre\_mex$ ，其中 $pre\_mex[i]$ 表示没有在 $P$ 内 $\texttt{前}$ $i$ 个元素内出现过的最小非负整数。

定义一个排列 $P$ 的后缀 $mex$ 序列为一个长度为 $n$ 的非负整数数组 $suf\_mex$ ，其中 $suf\_mex[i]$ 表示没有在 $P$ 内 $\texttt{后}$ $i$ 个元素内出现过的最小非负整数。

给你一个排列 $a$ ，定义两个排列 $P, Q$ 相似当且仅当它们的前缀 $mex$ 序列相等且后缀 $mex$ 序列同样相等，请你求出一个排列 $b$ 满足 $b$ 是字典序大于 $a$ 且与 $a$ 相似的字典序最小的排列。

特别地，当无解时，请你输出 $-1$ 表示没有这样的排列 $b$ 。

输入描述:

第一行输入一个整数  代表排列中的元素数量。
第二行输入  个互不相同的整数  代表排列元素。

输出描述:

输出一个长度为  的排列 ，表示答案。
特别地，当无解时输出 。

示例1

输入

复制

5
0 2 3 4 1

输出

复制

0 2 4 3 1

说明

示例2

输入

复制

5
0 1 2 3 4

输出

复制

-1

说明

容易证明，不存在一个字典序大于  的排列  与  相似，此时输出  表示无解

示例3

输入

复制

7
5 1 2 3 4 6 0

输出

复制

5 1 2 3 6 4 0

示例4

输入

复制

5
1 2 4 3 0

输出

复制

1 3 2 4 0

示例5

输入

复制

6
3 4 5 1 2 0

输出

复制

3 5 4 1 2 0

示例6

输入

复制

7
1 2 6 5 0 4 3

输出

复制

1 4 2 5 0 6 3

示例7

输入

复制

6
1 2 3 5 4 0

输出

复制

1 2 4 3 5 0