您有一副 $$$n$$$ 卡牌,并且您想将其重新排序为新卡牌。
每张卡的价值介于 $$$1$$$ 和 $$$n$$$ 之间,等于 $$$p_i$$$。所有 $$$p_i$$$ 都是成对不同的。一副牌中的牌是从下到上编号的,即。 e. $$$p_1$$$ 代表底牌,$$$p_n$$$ 代表顶牌。
在每个步骤中,您选择一些整数 $$$k > 0$$$,从原始牌组中取出顶部的 $$$k$$$ 卡,并将它们按照现在的顺序放置在新牌组的顶部。执行此操作直到原始牌组为空。 (请参阅注释部分以获得更好的理解。)
让我们将一副牌的顺序定义为 $$$\sum\limits_{i = 1}^{n}{n^{n - i} \cdot p_i}$$$。
给定原始牌组,输出使用上述操作可以制作的最大可能顺序的牌组。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) - 您拥有的牌组的大小。
第二行包含 $$$n$$$ 整数 $$$p_1, p_2,\dots, p_n$$$ ($$$1 \le p_i \le n$$$; $$$p_i \neq p_j$$$ if $$$i \neq j$$$) — 牌组中从下到上的牌值。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印具有最大可能顺序的卡片组。从下到上打印这副牌中卡片的值。
如果有多个答案,请打印其中任何一个。
示例
输入 #1
4 4 1 2 3 4 5 1 5 2 4 3 6 4 2 5 3 6 1 1 1
输出 #1
4 3 2 1 5 2 4 3 1 6 1 5 3 4 2 1
注意
在第一个测试用例中,最佳策略之一是下一个:
1. 从$$$p$$$上方取出$$$1$$$卡并将其移至$$$p'$$$:$$$p$$$变为$$$[1, 2, 3]$$$,$$$p'$$$变为$$$[4]$$$;
2. 从$$$p$$$上方取出$$$1$$$卡:$$$p$$$变为$$$[1, 2]$$$,$$$p'$$$变为$$$[4, 3]$$$;
3. 从$$$p$$$上方取出$$$1$$$卡:$$$p$$$变为$$$[1]$$$,$$$p'$$$变为$$$[4, 3, 2]$$$;
4. 从 $$$p$$$ 顶部取出 $$$1$$$ 卡:$$$p$$$ 变为空,$$$p'$$$ 变为 $$$[4, 3, 2, 1]$$$。
在第二个测试用例中,最佳策略之一是:
1. 从$$$p$$$顶部取出$$$4$$$卡并将其移至$$$p'$$$:$$$p$$$变为$$$[1]$$$,$$$p'$$$变为$$$[5,2,4,3]$$$;
2.从$$$p$$$顶部取出$$$1$$$卡并将其移至$$$p'$$$:$$$p$$$变为空,$$$p'$$$变为$$$[5,2,4,3,1]$$$;
在第三个测试用例中,最佳策略之一是:
1. 从$$$p$$$上方取出$$$2$$$牌并将其移至$$$p'$$$:$$$p$$$变为$$$[4, 2, 5, 3]$$$,$$$p'$$$变为$$$[6, 1]$$$;
2. 从$$$p$$$顶部取出$$$2$$$卡并将其移至$$$p'$$$:$$$p$$$变为$$$[4, 2]$$$,$$$p'$$$变为$$$[6, 1, 5, 3]$$$;
3. 从 $$$p$$$ 顶部取出 $$$2$$$ 卡并将其移至 $$$p'$$$:$$$p$$$ 变为空,$$$p'$$$ 变为 $$$[6, 1, 5, 3, 4, 2]$$$。