题目描述

本题译自 JOI 2013 Final T5「バブルソート」

冒泡排序是一种能对数列进行排序的算法。在使用冒泡排序对长为 $N$ 的数列 $A$ 进行升序排序时，如果相邻两个数中左边的数大于了右边的数，则交换这两个数的位置。每次从数列的前端开始扫描，当 $A_i>A_{i+1} (i=1,2,\cdots,N-1)$ ，就将这两个数交换。扫描进行 $N-1$ 次后，数列就一定满足升序排列。

对数列 $A$ 进行冒泡排序的交换次数表示：对数列 $A$ 进行以上所述算法时，整数被交换的次数。（冒泡排序的算法和实现包括循环顺序、范围和终止条件等。有时会存在细微差别。 但是，当应用于相同的数列时，整数的交换次数不会因这些情况的不同而改变。）

例如，以下为对长为 $N$ 的整数数列 $A$ 进行冒泡排序的程序（C 语言）。

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'$ 使用冒泡排序使其升序排列的交换次数的最小值。（请注意：开始时对数列 $A$ 中整数的交换并不需要交换相邻两个数。）

输入格式

输入标准如下：

• 第一行为一个整数 $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

数据范围与提示

对于 $10\%$ 的数据：

• $N \leq 1000$ 且对于任意 $i,j (1 \leq i < j \leq N)$ 满足 $A_i \not = A_j$

对于 $30\%$ 的数据：

• $N \leq 5000$ 且对于任意 $i,j (1 \leq i < j \leq N)$ 满足 $A_i \not = A_j$

对于 $80\%$ 的数据：

• 对于任意 $i,j (1 \leq i < j \leq N)$ 满足 $A_i \not = A_j$

对于 $100\%$ 的数据：

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$