AT_tupc2024_d Swap Counter

对于 $ (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 翻译