冒泡排序
题号：NC53186
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

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

输出描述:

输出一行一个整数：表示对数列A'进行冒泡排序的交换次数的最小值。
示例1

输入

复制 
5
10
3
6
8
1

输出

复制 
0

说明

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

输入

复制 
5
3
1
7
9
5

输出

复制 
2

说明

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

输入

复制 
3
1
2
3

输出

复制 
1

说明

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

备注:

对于的数据：
且对于任意满足
对于的数据：
且对于任意满足
对于的数据：
对于任意满足
对于的数据：


CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/2765