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 $ を満たすものが存在するか判定し、存在するならばそのようなもののうち辞書順で最小のものを求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ を空白区切りで出力せよ。

### Sample Explanation 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 $ は存在しません。 ### Constraints - $ 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 $ 以下