说明

冒泡排序 是一种对序列进行排序的算法。假设我们想将一个长度为 $N$ 的数列 $A$ 按升序排序。冒泡排序会检查相邻的两个数，如果它们的大小关系不正确，就交换它们的位置。这一过程是通过从前向后扫描数列来完成的。也就是说，如果存在 $A_i > A_{i+1}$ 的位置，就交换这两个数，并且按照 $i = 1, 2, \dots, N-1$ 的顺序对每个 $i$ 执行一次检查，这称为一次扫描。已知，重复进行 $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;
            }
        }
    }
}

任务

给定一个长度为 $N$ 的数列 $A$。假设通过交换数列 $A$ 中任意位置的两个整数一次（仅一次），得到一个新的数列 $A'$。编写一个程序，求出数列 $A'$ 的冒泡排序交换次数的最小值。（请注意，最初交换的两个整数不一定是相邻的。）

输入格式

从标准输入读取以下数据。

• 第一行包含一个整数 $N$。$N$ 表示数列 $A$ 的长度。
• 接下来的 $N$ 行中，第 $i$ 行 ($1 \leq i \leq N$) 包含一个整数 $A_i$。这表示数列 $A$ 的第 $i$ 个整数。

输出格式

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

5
10
3
6
8
1

0

5
3
1
7
9
5

2

3
1
2
3

1

提示

样例解释 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 完成