题目描述

你有一副包含 $n$ 张牌的牌堆，你希望将其重新排列成一个新的牌堆。

每张牌的数值为 $1$ 到 $n$ 之间的某个整数，记为 $p_i$。所有 $p_i$ 两两不同。牌堆中的牌从下到上编号，即 $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$，且 $i \neq j$ 时 $p_i \neq p_j$），表示从底到顶的牌面数值。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，输出一行，表示通过操作得到的序最大的牌堆，从底到顶输出牌面数值。

如果有多种方案，输出任意一种。

说明/提示

在第一个测试用例中，一种最优策略如下：

1. 从 $p$ 顶部取 $1$ 张牌放到 $p'$ 顶部：$p$ 变为 $[1, 2, 3]$，$p'$ 变为 $[4]$；
2. 再取 $1$ 张牌放到 $p'$ 顶部：$p$ 变为 $[1, 2]$，$p'$ 变为 $[4, 3]$；
3. 再取 $1$ 张牌放到 $p'$ 顶部：$p$ 变为 $[1]$，$p'$ 变为 $[4, 3, 2]$；
4. 再取 $1$ 张牌放到 $p'$ 顶部：$p$ 变为空，$p'$ 变为 $[4, 3, 2, 1]$。

最终，$p'$ 的序为 $4^3 \cdot 4 + 4^2 \cdot 3 + 4^1 \cdot 2 + 4^0 \cdot 1 = 256 + 48 + 8 + 1 = 313$。

在第二个测试用例中，一种最优策略如下：

1. 从 $p$ 顶部取 $4$ 张牌放到 $p'$ 顶部：$p$ 变为 $[1]$，$p'$ 变为 $[5, 2, 4, 3]$；
2. 再取 $1$ 张牌放到 $p'$ 顶部：$p$ 变为空，$p'$ 变为 $[5, 2, 4, 3, 1]$。

最终，$p'$ 的序为 $5^4 \cdot 5 + 5^3 \cdot 2 + 5^2 \cdot 4 + 5^1 \cdot 3 + 5^0 \cdot 1 = 3125 + 250 + 100 + 15 + 1 = 3491$。

在第三个测试用例中，一种最优策略如下：

1. 从 $p$ 顶部取 $2$ 张牌放到 $p'$ 顶部：$p$ 变为 $[4, 2, 5, 3]$，$p'$ 变为 $[6, 1]$；
2. 再取 $2$ 张牌放到 $p'$ 顶部：$p$ 变为 $[4, 2]$，$p'$ 变为 $[6, 1, 5, 3]$；
3. 再取 $2$ 张牌放到 $p'$ 顶部：$p$ 变为空，$p'$ 变为 $[6, 1, 5, 3, 4, 2]$。

最终，$p'$ 的序为 $6^5 \cdot 6 + 6^4 \cdot 1 + 6^3 \cdot 5 + 6^2 \cdot 3 + 6^1 \cdot 4 + 6^0 \cdot 2 = 46656 + 1296 + 1080 + 108 + 24 + 2 = 49166$。

由 ChatGPT 4.1 翻译

样例

4
4
1 2 3 4
5
1 5 2 4 3
6
4 2 5 3 6 1
1
1

4 3 2 1
5 2 4 3 1
6 1 5 3 4 2
1