問題文

長さ N の数列 A = (A_1, A_2, \ldots, A_N) が与えられます。1 \leq i < j \leq N かつ A_i > A_j を満たす整数の組 (i, j) の個数を求めてください。

制約

• 入力はすべて整数である
• 1 \leq N \leq 150000
• \bm{A} は \bm{(1, 2, \ldots, N)} を並べ替えた順列である

入力例 1

4
2 4 1 3

出力例 1

3

(i, j) = (1, 3), (2, 3), (2, 4) の 3 つが条件を満たします。

入力例 2

7
3 6 4 5 7 1 2

出力例 2

12