P13385 [GCJ 2011 Finals] Ace in the Hole

Amy 有一副包含 $N$ 张牌的牌堆，牌面数值为 $1$ 到 $N$。她将牌堆排列，使得任意长度为 $3$ 的递减子序列都不存在。例如，$1, 5, 4, 6, 3, 2$ 是非法排列，因为 $5, 3, 2$ 构成了长度为 $3$ 的递减子序列。 Amy 把这副牌交给了 Ben。Ben 知道这副牌没有长度为 $3$ 的递减子序列，但他不知道具体的排列顺序。他想找到数值为 $1$ 的那张牌。他的方法是每次任意选择一张牌，翻开查看其数值，然后重复此过程，直到找到数值为 $1$ 的牌。每一步，Ben 都会选择能使他在最坏情况下需要查看的牌数最少的那张牌。 后来 Ben 告诉你，他运气很差，在找到数值为 $1$ 的牌之前，不得不把 $N$ 张牌全部都看了一遍。给定 Ben 检查牌的顺序，请你推断每张牌的数值分别是多少。如果有多种可能，请输出字典序最大的那一种。 如果牌堆 $A$ 在第一个不同的位置上牌面数值大于牌堆 $B$，则称 $A$ 的字典序大于 $B$。 例如：$N = 3$，Ben 检查牌的顺序为 $2, 1, 3$（下标从 $1$ 开始）。那么牌的数值排列应为：$2, 3, 1$。 解释：如果第 $2$ 张牌是 $1$，Ben 会立刻停止。如果第 $2$ 张牌是 $2$，Ben 会知道第 $1$ 张牌一定是 $1$，因为排列 $(3, 2, 1)$ 存在长度为 $3$ 的递减子序列，因此不可能。因此，第 $2$ 张牌只能是 $3$。同理，第 $1$ 张牌也不能是 $1$，否则 Ben 会提前停止。因此，牌面数值应为 $2, 3, 1$。

第一行输入一个整数 $T$，表示测试用例的数量。接下来有 $T$ 组测试数据。每组测试数据第一行包含一个整数 $N$，表示牌的数量。第二行包含 $N$ 个用空格分隔的整数，表示 Ben 检查牌的顺序：第一个整数表示他首先检查的牌的位置（下标从 $1$ 开始），第二个整数表示他第二次检查的牌的位置，依此类推。

对于每个测试用例，输出一行，格式为 "Case #$x$: $y$"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是牌面数值的排列，用空格分隔。

**数据范围** - $1 \leq T \leq 100$ - 对于给定的 Ben 的检查顺序，至少存在一种满足所有条件（包括 Ben 必须检查 $N$ 张牌）的牌堆排列。 **小数据（20 分，测试点 1 - 可见）** - $1 \leq N \leq 8$ - 时间限制：3 秒。 **大数据（22 分，测试点 2 - 隐藏）** - $1 \leq N \leq 300$ - 时间限制：6 秒。 由 ChatGPT 4.1 翻译