P13257 [GCJ 2014 #2] Up and Down

给定一个由互不相同的整数构成的序列 $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$ 排列成一个“先升后降”序列所需的**最小交换次数**。

输入的第一行是测试用例数量 $T$。接下来是 $T$ 个测试用例。 每个测试用例的第一行是一个整数 $N$，表示序列中元素的个数。 下一行是 $N$ 个互不相同的整数，依次为 $A_1, A_2, \dots, A_N$。

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

**样例解释** - 在第一个样例中，原序列已经是目标形式（此处 $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 完成