P16631 [GKS 2017 #F] Kicksort

在 Kickstart，我们是著名的快速排序算法的爱好者，该算法从列表中选择一个基准值，根据其他值与基准值的比较结果将其移动到两个新列表之一，然后递归地对每个新列表进行排序。然而，算法可能会选择一个基准值，导致所有其他值最终都只进入两个新列表中的一个，这违背了分治策略的初衷。我们称这样的基准值为**最坏情况基准**。 为了尝试避免这个问题，我们创建了自己的变体 Kicksort。有人告诉我们，使用中间的值作为基准值效果很好，因此我们的算法如下： ``` Kicksort(A): // A 是一个有 E 个元素的 0 索引列表 如果 E ≤ 1，则返回 A。 否则： 创建空的新列表 B 和 C。 选择 A[floor((E-1)/2)] 作为基准值 P。 对于 i = 0 到 E-1，除了 i = floor((E-1)/2)： 如果 A[i] ≤ P，则将其追加到 B。 否则，将其追加到 C。 返回列表 Kicksort(B) + [P] + Kicksort(C)。 // [P] 是仅包含 P 的新列表；+ 表示连接 ``` 为了练习，我们尝试在 $1$ 到 $N$ 的排列列表上运行 Kicksort。不幸的是，看起来 Kicksort 仍然存在与快速排序相同的问题：有可能每个基准值都是**最坏情况基准**！ 例如，考虑列表 `1 4 3 2`。Kicksort 会选择 $4$ 作为基准值，所有其他值 `1 3 2` 都将进入两个新列表中的一个。然后，当在列表 `1 3 2` 上调用 Kicksort 时，它会选择 $3$，再次所有其他值都将进入两个新列表中的一个。最后，它会从列表 `1 2` 中选择 $1$，另一个值 $2$ 当然也只会进入两个新列表中的一个。在每种情况下，算法都会选择一个**最坏情况基准**。（注意，当对包含 $0$ 或 $1$ 个元素的列表调用 Kicksort 时，它根本不会选择基准值。） 请帮助我们进一步研究！给定一个 $1$ 到 $N$ 的排列，判断 Kicksort 是否只会选择**最坏情况基准**。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例；每个测试用例由两行组成。第一行包含一个整数 $N$：排列中元素的数量。第二行包含 $N$ 个整数 $A_i$，它们是 $1$ 到 $N$ 的一个排列。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 为 `YES`（如果 Kicksort 在对该列表排序时只会选择最坏情况基准）或 `NO`（否则）。

样例 #1 就是题目描述中给出的例子。 在样例 #2 中，我们的第一个基准值是 $1$，这是一个最坏情况基准，因为它使所有其他值 $2$、$3$、$4$ 都进入两个新列表中的一个。然而，在列表 $2$、$3$、$4$ 上调用 Kicksort 时，它会选择 $3$ 作为基准值。这不是一个最坏情况基准，因为它将 $2$ 放入一个新列表，将 $4$ 放入另一个。 在样例 #3 中，Kicksort 首先选择最坏情况基准 $2$，之后没有其他基准需要选择。 在样例 #4 中，Kicksort 首先选择 $2$，这不是一个最坏情况基准。 ### 限制条件 $A_i$ 是 $1$ 到 $N$ 的一个排列。 **小数据集（测试集 1 – 可见）** $1 \le T \le 32$。 $2 \le N \le 4$。 **大数据集（测试集 2 – 隐藏）** $1 \le T \le 100$。 $2 \le N \le 10000$。 翻译由 DeepSeek V4 Pro 完成