AT_joi2013ho5 バブルソート (Bubble Sort)

冒泡排序是一种对序列进行排序的算法之一。假设要将长度为 $N$ 的数列 $A$ 按升序排序。冒泡排序会检查相邻的两个数，如果它们的大小关系不正确，则交换它们的位置。这一操作会从数列的前端依次进行。也就是说，对于 $i = 1, 2, \ldots, N-1$，如果 $A_i > A_{i+1}$，就交换这两个数，这样的一次遍历称为一次扫描。已知重复进行 $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; } } } } ```

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

请输出一个整数，表示通过冒泡排序对数列 $A'$ 进行排序时的最小交换次数，其中 $A'$ 是将数列 $A$ 中任意两个整数交换一次后得到的新数列。输出结果占一行。

## 任务 给定一个长度为 $N$ 的数列 $A$。你可以将数列 $A$ 中任意两个位置的整数交换一次，得到数列 $A'$。请编写程序，求出数列 $A'$ 通过冒泡排序进行排序时所需的最小交换次数。（注意，最初交换的两个整数不一定是相邻的。） ## 限制 $2 \leq N \leq 100\,000$ $1 \leq A_i \leq 1\,000\,000\,000$ （注：移植自旧题时对限制进行了修正。） - - - - - - ## 评测标准 对于评测数据中 $10\%$ 的数据，满足 $N \leq 1\,000$，且任意 $i, j$ ($1 \leq i < j \leq N$) 满足 $A_i \neq A_j$。 对于评测数据中 $30\%$ 的数据，满足 $N \leq 5\,000$，且任意 $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$。 - - - - - - ## 样例解释 1 如果将数列 $A$ 的第一个 $10$ 和最后一个 $1$ 交换，则数列 $A'$ 就变成了已排序的序列，此时冒泡排序的交换次数为 $0$。 - - - - - - ## 样例解释 2 如果将数列 $A$ 的第 $3$ 个 $7$ 和最后一个 $5$ 交换，则数列 $A'$ 变为 $3, 1, 5, 9, 7$。此时 $A'$ 通过冒泡排序的交换次数为 $2$。 - - - - - - ## 样例解释 3 即使最初数列 $A$ 已经是有序的，在构造数列 $A'$ 时也必须进行一次交换。 由 ChatGPT 4.1 翻译