E - 転倒数
Editorial
/
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