Inversion Count (反転数)
昔々、とある神秘的な地に、マーリンという名の賢き魔術師が住んでいました。マーリンは順列の中に潜む隠れたパターンを見抜く特別な力を持っており、とりわけ「反転」の概念に強く興味を持っていました。
順列における反転 (inversion) とは、i < j かつ を満たす 2 つの要素 () のことです。反転の個数は、その順列が昇順に整列された状態からどのくらい離れているかを示しています。
マーリンは優れたプログラマーたちを試すため、次のような問題を出しました。1 から n までの整数による順列が与えられたとき、その順列に含まれる反転の数を求めなさい。
入力
最初の行には、順列のサイズを表す単一の整数
n (1 ≤ n ≤ 100 000) が与えられます。続く 2 行目には、順列を構成する n 個の整数がスペース区切りで与えられます。出力
与えられた順列に含まれる反転の総数を表す整数を 1 つ出力してください。
Examples (例)
Input | Output |
5
3 1 4 2 5 | 3 |
4
1 2 3 4 | 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB