P15810 [JOI 2013 Final] 冒泡排序 / Bubble Sort

**冒泡排序** 是一种对序列进行排序的算法。假设我们想将一个长度为 $N$ 的数列 $A$ 按升序排序。冒泡排序会检查相邻的两个数，如果它们的大小关系不正确，就交换它们的位置。这一过程是通过从前向后扫描数列来完成的。也就是说，如果存在 $A_i > A_{i+1}$ 的位置，就交换这两个数，并且按照 $i = 1, 2, \dots, N-1$ 的顺序对每个 $i$ 执行一次检查，这称为一次扫描。已知，重复进行 $N-1$ 次这样的扫描，就可以将数列按升序排序。 数列 $A$ 的**冒泡排序交换次数**，是指将上述算法应用于数列 $A$ 时，发生整数交换的次数。（已知的冒泡排序算法及其实现可能在循环顺序、范围以及终止条件等方面存在细微差异。但已知的是，当应用于同一数列时，整数交换次数不会因这些差异而改变。） 例如，以下程序是用 C 语言编写的、使用冒泡排序对长度为 $n$ 的整数数组 $a$ 进行排序的函数。 ```cpp void bubble_sort(int *a, int n) { int i, j; for (i = 0; i < n - 1; ++i) { for (j = 0; j < n - 1; ++j) { if (a[j] > a[j + 1]) { /* 以下 3 行对应一次整数交换 */ int x = a[j]; a[j] = a[j + 1]; a[j + 1] = x; } } } } ``` ### 任务 给定一个长度为 $N$ 的数列 $A$。假设通过交换数列 $A$ 中任意位置的两个整数一次（仅一次），得到一个新的数列 $A'$。编写一个程序，求出数列 $A'$ 的冒泡排序交换次数的最小值。（请注意，最初交换的两个整数不一定是相邻的。）

从标准输入读取以下数据。 - 第一行包含一个整数 $N$。$N$ 表示数列 $A$ 的长度。 - 接下来的 $N$ 行中，第 $i$ 行 ($1 \leq i \leq N$) 包含一个整数 $A_i$。这表示数列 $A$ 的第 $i$ 个整数。

向标准输出输出一行，包含一个整数，表示数列 $A'$ 的冒泡排序交换次数的最小值。

### 样例解释 1 如果交换数列 $A$ 开头的 $10$ 和结尾的 $1$，那么数列 $A'$ 将成为已排序的序列，其冒泡排序交换次数为 $0$。 ### 样例解释 2 如果交换数列 $A$ 中第三个的 $7$ 和最后一个的 $5$，那么数列 $A'$ 变为 $3, 1, 5, 9, 7$。$A'$ 的冒泡排序交换次数为 $2$。 ### 样例解释 3 即使数列 $A$ 最初就是已排序的，在构造数列 $A'$ 时也必须进行一次交换。 ### 限制 $1 \leq N \leq 100\,000$　数列 $A$ 的长度 $1 \leq A_i \leq 1\,000\,000\,000$　数列 $A$ 中数字的大小 ### 评分标准 在评分数据中，占分值 10% 的部分满足 $N \leq 1000$，且对于任意 $i, j$ ($1 \leq i < j \leq N$) 有 $A_i \neq A_j$。 在评分数据中，占分值 30% 的部分满足 $N \leq 5000$，且对于任意 $i, j$ ($1 \leq i < j \leq N$) 有 $A_i \neq A_j$。 在评分数据中，占分值 80% 的部分满足对于任意 $i, j$ ($1 \leq i < j \leq N$) 有 $A_i \neq A_j$。 --- 翻译由 DeepSeek V3.2 完成