题目描述

在 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（否则）。

4
4
1 4 3 2
4
2 1 3 4
2
2 1
3
1 2 3

Case #1: YES
Case #2: NO
Case #3: YES
Case #4: 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 完成