题目描述

冒泡排序是对序列进行排序的算法之一。假设我们要将长度为 $N$ 的数列 $A$ 按升序排序。在冒泡排序中，如果相邻的 $2$ 个数的大小关系发生倒置，就交换它们的位置。从前向后依次扫描数列，即对于 $i = 1, 2, \dots, N - 1$ 按此顺序，若满足 $A_i > A_{i+1}$ 则交换这 $2$ 个数，这样算作一次扫描。众所周知，将这一扫描重复 $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]) {
        /* The following 3 lines correspond to 1 swap of integers */
        int x = a[j];
        a[j] = a[j + 1];
        a[j + 1] = x;
      }
    }
  }
}

任务

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

限制

• $1 \le N \le 100000$：数列 $A$ 的长度。
• $1 \le A_i \le 1000000000$：数列 $A$ 中包含的数字的大小。

输入格式

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

• 第 $1$ 行写有整数 $N$。$N$ 表示数列 $A$ 的长度。
• 接下来的 $N$ 行中的第 $i$ 行（$1 \le i \le N$）写有整数 $A_i$。这表示数列 $A$ 的第 $i$ 个整数。

输出格式

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

评分标准

• 在评测数据中，占总分 $10\%$ 的数据满足 $N \le 1000$，且对于任意 $i, j$（$1 \le i < j \le N$）满足 $A_i \ne A_j$。
• 在评测数据中，占总分 $30\%$ 的数据满足 $N \le 5000$，且对于任意 $i, j$（$1 \le i < j \le N$）满足 $A_i \ne A_j$。
• 在评测数据中，占总分 $80\%$ 的数据对于任意 $i, j$（$1 \le i < j \le N$）满足 $A_i \ne A_j$。

样例

样例输入 1

5
10
3
6
8
1

样例输出 1

0

如果将数列 $A$ 开头的 $10$ 与末尾的 $1$ 交换，则数列 $A'$ 变为已排好序的序列，冒泡排序的交换次数为 $0$。

样例输入 2

5
3
1
7
9
5

样例输出 2

2

将数列 $A$ 的第 $3$ 个数 $7$ 与最后的 $5$ 交换后，数列 $A'$ 变为 $3, 1, 5, 9, 7$。$A'$ 通过冒泡排序进行的交换次数为 $2$。

样例输入 3

3
1
2
3

样例输出 3

1

即使数列 $A$ 从一开始就是排好序的，在构造数列 $A'$ 时也必须进行交换。