AT_joi2013ho5.バブルソート (Bubble Sort)

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

数列 $A$ 通过冒泡排序进行交换的次数，指的是将上述算法应用于数列 $A$ 时，整数之间发生交换的总次数。（虽然冒泡排序的算法和实现在循环顺序、范围以及终止条件等细节上可能有所不同，但已知对同一个数列应用时，整数交换的总次数不会因这些差异而改变。）

例如，以下程序是用 C 语言编写的函数，用冒泡排序对长度为 n 的整数数组 a 进行排序。

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 翻译