Bubble Sort

Bubble sort is one of the simplest sorting algorithms, described by the pseudocode below. Whenever two adjacent elements are out of order and get swapped, the swap counter increases by one.

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 pair is out of order, so swap the two elements. */
                /* This increases the swap count by one. */
                int x = a[j];
                a[j] = a[j + 1];
                a[j + 1] = x;
            }
        }
    }
}

Given an array $A$ of length $n$, define an array $A^$ as follows. Choose two indices $i$ and $j$ with $1 \le i < j \le n$, and swap the $i$-th and $j$-th elements of $A$ exactly once; the resulting array is $A^$.

Among all possible arrays $A^*$, output the smallest number of swaps that the bubble sort above would perform.

The first line contains an integer $N$. Each of the next $N$ lines contains one element of the array $A$, given in the order $A_1, A_2, \ldots, A_N$ (one per line).

Print the minimum bubble-sort swap count over all arrays $A^*$.

• $1 \le N \le 100{,}000$
• $1 \le A_i \le 1{,}000{,}000{,}000$