버블 정렬

버블 정렬은 아래 의사 코드로 표현되는 가장 단순한 정렬 알고리즘 중 하나이다. 이 코드에서는 이웃한 두 원소의 순서가 잘못되어 서로 맞바꿀 때마다 교환 횟수가 1씩 증가한다.

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]) {
                /* 순서가 잘못된 쌍이므로 두 원소를 맞바꾼다. */
                /* 이때 교환 횟수가 1 증가한다. */
                int x = a[j];
                a[j] = a[j + 1];
                a[j + 1] = x;
            }
        }
    }
}

길이가 $n$인 배열 $A$가 주어졌을 때, 배열 $A^*$를 다음과 같이 정의한다. 두 인덱스 $i$, $j$ ($1 \le i < j \le n$)를 골라 $A$의 $i$번째 원소와 $j$번째 원소를 정확히 한 번 맞바꾼 배열이 $A^*$이다.

가능한 모든 $A^*$ 중에서, 위 버블 정렬을 수행했을 때의 교환 횟수가 가장 작은 값을 출력하라.

첫째 줄에 정수 $N$이 주어진다. 이어지는 $N$개의 줄에 배열 $A$의 원소가 $A_1, A_2, \ldots, A_N$ 순서로 한 줄에 하나씩 주어진다.

모든 $A^*$ 중 버블 정렬 교환 횟수가 최소가 되는 값을 한 줄에 출력한다.

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