对于 $ (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 $，如果存在则输出字典序最小的满足条件的 $ P $。

有 $ T $ 组测试数据，请分别作答。

输入按如下格式从标准输入给出。

$ T $
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每组测试数据格式如下：

$ N $ $ B_1 $ $ B_2 $ $ \dots $ $ B_{N-1} $

输出 $ T $ 行，对于每个测试数据，第 $ i $ 行输出一行。如果不存在满足条件的排列，输出 -1。否则输出满足条件的字典序最小的 $ P $，用空格隔开。

样例解释 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 $ 的字典序最小结果。

对于第 $ 2 $ 个测试点， $ f(P)=(2,0,2,4) $ 的排列 $ P $ 不存在。

数据范围

• $ 1 \leq T \leq 1.5 \times 10^5 $
• $ 2 \leq N \leq 3 \times 10^5 $
• $ 0 \leq B_i \leq N-1 $
• 所有输入均为整数
• 所有测试数据中 $ N $ 之和不超过 $ 3 \times 10^5 $。

由 ChatGPT 5 翻译