Description

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$。

Input Format

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

Output Format

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

3
3
2 1 3
1
1
3
3 2 1

Case #1: 2 3 1
Case #2: 1
Case #3: 1 3 2

Hint

数据范围

• $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 翻译