0276 - バブルソート (Bubble Sort)

問題

バブルソートとは，列をソートするアルゴリズムの 1 つである．長さ N の数列 A を昇順にソートしたいとしよう．バブルソートは，隣り合う 2 つの数で大小関係が崩れているものがあれば，それらの位置を交換する．これを，数列を前から順に走査しながら行う．すなわち，A_i > A_i+1 となっている場所があれば，その 2 数を交換するということを，i = 1, 2, . . . , N - 1 に対してこの順で行うのが 1 回の走査である．この走査を 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 行が 1 回の整数の交換に相当 */
        int x = a[j];
        a[j] = a[j + 1];
        a[j + 1] = x;
      }
    }
  }
}

課題

　長さ N の数列 A が与えられる．数列 A の任意の場所の 2 つの整数を 1 回だけ交換した数列 A′ を作るとする．数列 A′ のバブルソートによる交換回数の最小値を求めるプログラムを作成せよ．（最初に交換する 2 つの整数は必ずしも隣り合っている必要はないことに注意せよ．）

制限

1 ≤ N ≤ 100 000  数列 A の長さ
1 ≤ A_i ≤ 1 000 000 000  数列 A に含まれる数字の大きさ

入力

　標準入力から以下のデータを読み込め．

• 1 行目には，整数 N が書かれている．N は数列 A の長さを表す．
• 続く N 行のうちの i 行目 (1 ≤ i ≤ N) には，整数 A_i が書かれている．これは数列 A の i 番目の整数を表す．

出力

　標準出力に，数列 A′ のバブルソートによる交換回数の最小値を表す整数を 1 行で出力せよ．

採点基準

　採点用データのうち，配点の 10 %分については，N ≤ 1 000 を満たし，任意の i, j (1 ≤ i < j ≤ N) について A_i ≠ A_j を満たす．
　採点用データのうち，配点の 30 %分については，N ≤ 5 000 を満たし，任意の i, j (1 ≤ i < j ≤ N) について A_i ≠ A_j を満たす．
　採点用データのうち，配点の 80 %分については，任意の i, j (1 ≤ i < j ≤ N) について A_i ≠ 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′ を作る際に交換を行わなければならない．