陈列记录 - 代码源竞赛平台

题目描述

展柜中有 $n$ 个从左到右排列的位置，编号为 $1,2,\ldots,n$。工作人员要把编号为 $1,2,\ldots,n$ 的展品各放入一个位置，记位置 $i$ 上的展品编号为 $p_i$。

一份陈列记录给出了 $n-2$ 个下标 $m_1,m_2,\ldots,m_{n-2}$。对于每个 $1\le i\le n-2$，都有 $i\le m_i\le i+2$，并要求 $p_{m_i}$ 是 $p_i,p_{i+1},p_{i+2}$ 中第二小的数。

请构造一个符合记录的排列 $p$。满足条件的排列可能不唯一，输出任意一个即可。若不存在满足条件的排列，输出 $-1$。

输入格式

第一行包含一个正整数 $n$，为展柜中的位置数。

第二行包含 $n-2$ 个正整数 $m_1,m_2,\ldots,m_{n-2}$。其中 $m_i$ 表示位置 $i,i+1,i+2$ 上的三个展品中，编号第二小的展品所在的位置。

输出格式

若不存在符合记录的排列，输出一行一个整数 $-1$。

否则输出一行 $n$ 个正整数 $p_1,p_2,\ldots,p_n$，表示从左到右各位置上的展品编号。

样例

5
2 4 4

1 3 5 4 2

3
1

2 1 3

数据规模

本题各子任务单独计分。须通过某子任务包含的所有测试点，方可获得该子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$20$	$9$	无
$2$	$15$	$2\times 10^5$	A
$3$	$25$	$2000$	无
$4$	$40$	$2\times 10^5$

特殊性质 A：对于每个 $1\le i\le n-2$，都有 $m_i=i+1$。

对于 $100\%$ 的数据，$3\le n\le 2\times 10^5$，对于每个 $1\le i\le n-2$，都有 $i\le m_i\le i+2$。输入中的所有数均为整数。