題目描述

冒泡排序係將序列排序嘅演算法之一。假設我哋想將長度係 $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'$ 嗰陣都一定要進行交換。