配点 : 100 点
問題文
(1,2,\dots,M) 的排列 给出了 Q=(Q_1,Q_2,\dots,Q_M) 关于,以长度 M-1 序列 使用 f(Q) 如下。 当
- 长度 小于或等于 M-1 序列 使用 X 该值应乘以 X=(0,0,\dots,0) 初始化后,按照如下顺序进行
- 执行以下操作。
重复 M-1 次
- i=1,2,\dots,M-1 ,交换
- Q_i > Q_{i+1} 如果 Q_i 和 按字典顺序比较 Q_{i+1} ,添加X_i 至 该值是 1 ,如果是
- Q_i < Q_{i+1} 则不做任何操作,判断是否存在满足
- i=1,2,\dots,M-1 ,交换
- 决赛 X 该值应乘以 f(Q) 成为
长度 小于或等于 N-1 序列 使用 B=(B_1,B_2,\dots,B_{N-1}) 。 对于(1,2,\dots,N) 的排列 给出了 P 找出可被 f(P)=B 的对象,如果存在,请求出这些对象中字典序最小的那个。对于第
T 给出若干测试用例,请分别求出答案。
制約
- 1 \leq T \leq 1.5 \times 10^5
- 2 \leq N \leq 3 \times 10^5
- 0 \leq B_i \leq N-1
- 所有输入均为整数
- 1 包含在输入文件中的 N 的总和是 3 \times 10^5 以下
入力
输入是按以下格式从标准输入给出的。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例以如下形式给出。
N
B_1 B_2 \dots B_{N-1}
出力
T 行。i=1,2,\dots,T 反对 i 在线 i 个测试用例,如果不存在满足条件的排列,则为 -1 ,如果存在,则为满足条件的字典序最小的 P 以空格分隔。
入力例 1
3 4 2 1 1 5 2 0 2 4 6 2 3 2 1 1
出力例 1
3 2 4 1 -1 3 5 4 2 6 1
1 个测试用例关于 P=(3,2,4,1) 什么时候 f(P) 的计算如下,第
- 简介 X=(0,0,0) 是
- 1 次操作如下,先加上
- P_1 > P_2 所以 X_1 至
该值是 1 ,再交换P_1 和
按字典顺序比较 P_2 ,由于
- X=(1,0,0),P=(2,3,4,1) 变为
- P_2 < P_3 所以不做任何事情,最终得到
- P_3 > P_4 所以 X_3 至
该值是 1 ,再交换P_3 和
按字典顺序比较 P_4 ,由于
- X=(1,0,1),P=(2,3,1,4) 变为
- P_1 > P_2 所以 X_1 至
该值是 1 ,再交换P_1 和
按字典顺序比较 P_2 ,由于
- 2 次操作如下,先加上
- P_1 < P_2 所以不做任何事情,最终得到
- P_2 > P_3 所以 X_2 至
该值是 1 ,再交换P_2 和
按字典顺序比较 P_3 ,由于
- X=(1,1,1),P=(2,1,3,4) 变为
- P_3 < P_4 所以不做任何事情,最终得到
- 3 次操作如下,先加上
- P_1 > P_2 所以 X_1 至
该值是 1 ,再交换P_1 和
按字典顺序比较 P_2 ,由于
- X=(2,1,1),P=(1,2,3,4) 变为
- P_2 < P_3 所以不做任何事情,最终得到
- P_3 < P_4 所以不做任何事情,最终得到
- P_1 > P_2 所以 X_1 至
该值是 1 ,再交换P_1 和
按字典顺序比较 P_2 ,由于
因此 连接 f(P) = (2,1,1) 。特别地,这是 P 是 在 f(P)=B 小于 P 中字典序最小的。
2 个测试用例关于 f(P)=(2,0,2,4) 所组成的排列 P 不存在。