E - 転倒数

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200

問題文

長さ N の順列 P = p_1, p_2, ..., p_N が与えられます。長さ N の順列であって、P より辞書順で小さいか等しいもの全てについて転倒数を求め、その和を答えてください。ただし答えはとても大きくなることがあるので、10^9 + 7 で割った余りを出力してください。

ただし、順列 X = x_1, x_2, ..., x_N の転倒数とは、1 \leq i < j \leq N かつ x_i > x_j を満たす整数 i, j の組の個数のことです。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq p_i \leq N
  • 入力は全て整数である。
  • p_1, p_2, ..., p_N は順列である。

入力

入力は以下の形式で標準入力から与えられる。

N
p_1 p_2 ... p_N

出力

長さ N の順列であって、順列 P より辞書順で小さいか等しいもの全てについて転倒数を求め、その和を 10^9 + 7 で割った余りを出力せよ。


入力例1

3
2 1 3

出力例1

2

順列 (2, 1, 3) より辞書順で小さいか等しい、長さ 3 の順列は (1, 2, 3), (1, 3, 2), (2, 1, 3)3 種類です。

これらの順列の転倒数はそれぞれ 0, 1, 1 なので、答えは 0 + 1 + 1 = 2 となります。


入力例2

4
1 2 3 4

出力例2

0

入力例3

8
5 6 2 7 1 3 8 4

出力例3

281881