← 返回题目列表

Codeforces · 1492/B

B. 卡组

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

您有一副 $$$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]$$$。