反転回数（隣接交換ソート）

N 個の整数からなる数列 A1, A2, …, AN が与えられます。
この数列を昇順に並べ替えるために必要な 隣接要素の交換回数を求めてください。

入力

N
A1 A2 ... AN

• 1 行目に整数 N (2 ≤ N ≤ 1000)
• 2 行目に N 個の整数 Ai (−10^6 ≤ Ai ≤ 10^6)

出力

昇順に並べ替えるために必要な最小の隣接交換回数を出力せよ。

入力例1

5
3 1 4 2 5

出力例1

3

（swap: [3,1,4,2,5] → [1,3,4,2,5] → [1,3,2,4,5] → [1,2,3,4,5]）

入力例2

4
1 2 3 4

出力例2

0

（すでにソート済み）

入力例3

3
3 2 1

出力例3

3

（swap: [3,2,1] → [2,3,1] → [2,1,3] → [1,2,3]）

ポイント

• この問題は「反転数（inversion number）」を数える問題と同じ。
• O(N^2) のループで十分解けるが、工夫すれば O(N log N) でも解ける（応用）。
• バブルソートの交換回数＝反転数 というつながりを学べる。

ケン

ヨワモンのパートナー

ヨワモンのパートナー