构造
时间限制: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 - 1n 个整数、按任意顺序组成的数组,其中每个整数恰好出现一次。例如,\{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
 

输入描述:

第一行输入一个整数 n\ (1 \leqq n \leqq 10^5) 代表排列中的元素数量。
第二行输入 n 个互不相同的整数 a_1,a_2,\cdots,a_n\ (0 \leqq a_i \lt n) 代表排列元素。

输出描述:

输出一个长度为 n 的排列 b,表示答案。
特别地,当无解时输出 -1
示例1

输入

复制
5
0 2 3 4 1

输出

复制
0 2 4 3 1

说明

pre\_mex_a = (1,1,1,1,5)
suf\_mex_a = (0,0,0,0,5)
示例2

输入

复制
5
0 1 2 3 4

输出

复制
-1

说明

容易证明,不存在一个字典序大于 a 的排列 b 与 a 相似,此时输出 -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