反転数

数列 $A = \{a_0, a_1, ... a_{n-1}\}$ について、$a_i > a_j$ かつ $i < j$ である組 $(i, j)$ の個数を反転数と言います。反転数は次のバブルソートの交換回数と等しくなります。

bubbleSort(A)
  cnt = 0 // 反転数
  for i = 0 to A.length-1
    for j = A.length-1 downto i+1
      if A[j] < A[j-1]
	swap(A[j], A[j-1])
	cnt++

  return cnt

数列 $A$ が与えられるので、$A$ の反転数を求めてください。上の疑似コードのアルゴリズムをそのまま実装するとTime Limit Exceeded になることに注意してください。

入力

１行目に数列 $A$ の長さ $n$ が与えられます。２行目に $a_i (i = 0, 1, .. n-1)$ が空白区切りで与えられます。

出力

反転数を１行に出力してください。

制約

• $ 1 \leq n \leq 200,000$
• $ 0 \leq a_i \leq 10^9$
• $a_i$ はすべて異なる値である

入力例 1

5
3 5 2 1 4

出力例 1

6

入力例 2

3
3 1 2

出力例 2

2

---