Description

给定一个由互不相同的整数构成的序列 $A = [A_1, A_2, \dots, A_N]$，你希望将其重新排列成一个“先升后降”的序列（即存在某个下标 $m$，满足 $1 \leq m \leq N$，使得 $A_1 < A_2 < \dots < A_m > A_{m+1} > \dots > A_N$）。

你只能通过每次交换两个相邻元素的方式来进行重排。你特别感兴趣的是：将序列 $A$ 排列成一个“先升后降”序列所需的最小交换次数。

Input Format

输入的第一行是测试用例数量 $T$。接下来是 $T$ 个测试用例。

每个测试用例的第一行是一个整数 $N$，表示序列中元素的个数。

下一行是 $N$ 个互不相同的整数，依次为 $A_1, A_2, \dots, A_N$。

Output Format

对于每个测试用例，输出一行，格式为 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是将序列 $A$ 排列成“先升后降”序列所需的最小交换次数。

2
3
1 2 3
5
1 8 10 3 7

Case #1: 0
Case #2: 1

Hint

样例解释

• 在第一个样例中，原序列已经是目标形式（此处 $m=N=3$），无需进行任何交换，答案为 $0$。
• 在第二个样例中，将 $3$ 与 $7$ 交换即可构成“先升后降”序列（此时 $m=3$），因此最小交换次数为 $1$。

限制条件

• $1 \leq T \leq 100$
• $1 \leq A_i \leq 10^9$
• 所有 $A_i$ 均互不相同

Small 数据集（7 分）

• 时间限制：60 3 秒
• $1 \leq N \leq 10$

Large 数据集（11 分）

• 时间限制：120 5 秒
• $1 \leq N \leq 1000$

翻译由 ChatGPT-4o 完成