題目描述

氣泡排序是對序列進行排序的演算法之一。假設我們要將長度為 $N$ 的數列 $A$ 按升序排序。在氣泡排序中，如果相鄰的 $2$ 個數的大小關係顛倒，就交換它們的位置。從前向後依序掃描數列，即對於 $i = 1, 2, \dots, N - 1$ 按此順序，若滿足 $A_i > A_{i+1}$ 則交換這 $2$ 個數，這樣算作一次掃描。眾所周知，將此掃描重複 $N - 1$ 次即可將數列按升序排序。

數列 $A$ 透過氣泡排序進行的交換次數，是指對數列 $A$ 套用上述演算法時發生整數交換的次數。（雖然被稱為氣泡排序的演算法及其實作可能在迴圈順序、範圍及終止條件等細節上存在差異，但已知對同一數列套用時，整數的交換次數不會因這些差異而改變。）

例如，下面的程式是用 C 語言編寫的使用氣泡排序對長度為 n 的整數陣列 a 進行排序的函式。

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 following 3 lines correspond to 1 swap of integers */
        int x = a[j];
        a[j] = a[j + 1];
        a[j + 1] = x;
      }
    }
  }
}

任務

給定長度為 $N$ 的數列 $A$。假設將數列 $A$ 中任意位置的 $2$ 個整數恰好交換 $1$ 次得到數列 $A'$。請編寫程式，求出數列 $A'$ 透過氣泡排序進行的交換次數的最小值。（注意：最初交換的 $2$ 個整數不一定是相鄰的。）

限制

• $1 \le N \le 100000$：數列 $A$ 的長度。
• $1 \le A_i \le 1000000000$：數列 $A$ 中包含的數字的大小。

輸入格式

從標準輸入讀取以下資料：

• 第 $1$ 行寫有整數 $N$。$N$ 表示數列 $A$ 的長度。
• 接下來的 $N$ 行中的第 $i$ 行（$1 \le i \le N$）寫有整數 $A_i$。這表示數列 $A$ 的第 $i$ 個整數。

輸出格式

向標準輸出以 $1$ 行輸出一個整數，表示數列 $A'$ 透過氣泡排序進行的交換次數的最小值。

評分標準

• 在評測資料中，佔總分 $10\%$ 的資料滿足 $N \le 1000$，且對於任意 $i, j$（$1 \le i < j \le N$）滿足 $A_i \ne A_j$。
• 在評測資料中，佔總分 $30\%$ 的資料滿足 $N \le 5000$，且對於任意 $i, j$（$1 \le i < j \le N$）滿足 $A_i \ne A_j$。
• 在評測資料中，佔總分 $80\%$ 的資料對於任意 $i, j$（$1 \le i < j \le N$）滿足 $A_i \ne A_j$。

範例

範例輸入 1

5
10
3
6
8
1

範例輸出 1

0

如果將數列 $A$ 開頭的 $10$ 與末尾的 $1$ 交換，則數列 $A'$ 變為已排好序的序列，氣泡排序的交換次數為 $0$。

範例輸入 2

5
3
1
7
9
5

範例輸出 2

2

將數列 $A$ 的第 $3$ 個數 $7$ 與最後的 $5$ 交換後，數列 $A'$ 變為 $3, 1, 5, 9, 7$。$A'$ 透過氣泡排序進行的交換次數為 $2$。

範例輸入 3

3
1
2
3

範例輸出 3

1

即使數列 $A$ 從一開始就是排好序的，在構造數列 $A'$ 時也必須進行交換。