题目描述

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

冒泡排序是一种能对数列进行排序的算法。在使用冒泡排序对长为 $ N $ 的数列 $ A $ 进行升序排序时，如果相邻两个数中左边的数大于了右边的数，则交换这两个数的位置。每次从数列的前端开始扫描，当 $ Ai>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' $ 进行冒泡排序的交换次数的最小值。

样例 1

input

5
10
3
6
8
1

output

0

将数列 $ A $ 开头的 $ 10 $ 和最后的 $ 1 $ 交换，数列 $ A' $ 就已经是升序的了。冒泡排序的交换次数为 $ 0 $ 。

样例 2

input

5
3
1
7
9
5

output

2

将数列 $ A $ 第 $ 3 $ 个数 $ 7 $ 和最后一个数 $ 5 $ 交换，数列 $ A' $ 就成了 $ 3,1,5,9,7 $ 。 $ A' $ 的冒泡排序交换次数为 $ 2 $ 。

样例 3

input

3
1
2
3

output

1

虽然一开始数列 $ A $ 就是升序排列的，但是还是必须交换其中两个数构成数列 $ A' $ 。

数据范围与提示

对于 $ 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 $