← 返回题目列表

AtCoder · tupc2024_d

D. 交换计数器

中文机器翻译题面 查看原题

配点 : 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} 则不做任何操作,判断是否存在满足
  • 决赛 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) 变为
  • 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 所以不做任何事情,最终得到

因此 连接 f(P) = (2,1,1) 。特别地,这是 P 是 在 f(P)=B 小于 P 中字典序最小的。

2 个测试用例关于 f(P)=(2,0,2,4) 所组成的排列 P 不存在。