Subarray Inversion Count

2 secs 1024 MB
sgsw

問題文


自然数と、長さの順列が与えられます。(この時、にはからまでの数がちょうど回ずつ出てきます。)

なる自然数に対して、 としてを定義します。

このような通り考えられますが、 その全てに対する転倒数の合計値をで割ったあまりを求めてください。

入力


N
P_1 P_2 ... P_N

制約


は長さの順列、すなわちソートするととなる。

入力1
4
1 4 3 2
出力1
9

対象となる部分列は 個であり、それぞれの部分列に対する転倒数の値は、

順番に個であり、その合計値はです。

入力2
2
1 2
出力2
0

対象となる部分列は個で、この部分列の転倒数の値はです。

入力3
2
2 1
出力3
1

対象となる部分列は個で、この部分列の転倒数の値はです。

入力4
20
13 2 18 10 1 11 8 17 14 4 7 12 19 3 20 9 16 5 6 15
出力4
3426

提出


Go (1.14)