Description

在 Code Jam 的秘密算法实验室里，我们花费了无数小时，致力于解决当今最复杂的问题之一：高效地将一个整数序列按非递减顺序排序。我们仔细研究了经典的冒泡排序算法，并很高兴地宣布一种新变体。

标准冒泡排序算法的基本操作是检查一对相邻的数字，如果左边的数字大于右边的数字，则交换这对数字。而我们的算法会检查一组三个相邻的数字，如果最左边的数字大于最右边的数字，就将整个三元组反转。由于我们的算法是“三元组冒泡排序”，我们将其简称为 Trouble Sort。

  TroubleSort(L): // L 是一个从 0 开始编号的整数列表
    let done := false
    while not done:
      done = true
      for i := 0; i < len(L)-2; i++:
        if L[i] > L[i+2]:
          done = false
          reverse the sublist from L[i] to L[i+2], inclusive

例如，对于 $L = 5\ 6\ 6\ 4\ 3$，Trouble Sort 的执行过程如下：

• 第一轮：
  • 检查 $5\ 6\ 6$，无需操作：$5\ 6\ 6\ 4\ 3$
  • 检查 $6\ 6\ 4$，发现 $6 > 4$，反转三元组：$5\ 4\ 6\ 6\ 3$
  • 检查 $6\ 6\ 3$，发现 $6 > 3$，反转三元组：$5\ 4\ 3\ 6\ 6$
• 第二轮：
  • 检查 $5\ 4\ 3$，发现 $5 > 3$，反转三元组：$3\ 4\ 5\ 6\ 6$
  • 检查 $4\ 5\ 6$，无需操作：$3\ 4\ 5\ 6\ 6$
  • 检查 $5\ 6\ 6$，无需操作：$3\ 4\ 5\ 6\ 6$
• 第三轮检查所有三元组均无需操作，算法终止。

我们原本期待在夏威夷举办的排序特别兴趣小组会议上展示 Trouble Sort，但我们的一个实习生刚刚指出了一个问题：Trouble Sort 可能无法正确地对序列进行排序！例如，考虑序列 $8\ 9\ 7$。

我们需要你的帮助来进一步研究。给定一个长度为 $\mathbf N$ 的整数序列，判断 Trouble Sort 是否能将该序列正确地按非递减顺序排序。如果不能，请在算法结束后找出第一个排序错误的位置（从 0 开始计数）：即第一个比其后一个数大的数的下标。

Input Format

输入的第一行包含测试用例的数量 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试数据。每组测试数据包含两行：第一行为一个整数 $\mathbf{N}$，表示序列的长度，第二行为 $\mathbf{N}$ 个整数 $\mathbf{V}_\mathbf{i}$，表示序列中的元素。

Output Format

对于每组测试数据，输出一行，格式为 Case #x: y，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为 ok（如果 Trouble Sort 能正确排序），或者为第一个排序错误的下标（从 0 开始计数），如上所述。

2
5
5 6 8 4 3
3
8 9 7

Case #1: OK
Case #2: 1

Hint

样例解释

样例 Case #1 与题目描述中的第一个例子类似。Trouble Sort 能正确排序该序列，因此输出 ok。

样例 Case #2 是题目描述中的第二个例子。Trouble Sort 无法正确排序该序列，最终结果为 $7\ 9\ 8$。$9$ 是第一个比下一个数大的数，因此第一个排序错误的下标为 $1$。

数据范围

• $1 \leq T \leq 100$。
• 对所有 $i$，$0 \leq V_i \leq 10^9$。

测试点 1（8 分，可见）

• $3 \leq N \leq 100$。
• 整个测试点的时间限制：10 秒。

测试点 2（15 分，隐藏）

• $3 \leq N \leq 10^5$。
• 整个测试点的时间限制：20 秒。

特别说明

注意，本题的测试点 2 输入量很大，因此使用非缓冲输入可能导致读取速度较慢。此外，请注意某些编程语言默认的输入缓冲区较小。

由 ChatGPT 4.1 翻译