配点 : $1700$ 点

問題文

すぬけ君は、長さ $N$ の整数列 $A$ を持っています。 すぬけ君は、$(1, 2, ..., N)$ の順列 $P$ であって、次の条件を満たすものが好きです。

• 全ての $i$ ( $1 \leq i \leq N$ ) について、$P_i \leq A_i$

すぬけ君は、条件を満たすような順列の転倒数 ( ※ ) に興味を持ちました。 すぬけ君のために、条件を満たすような全ての順列について転倒数を求め、その総和を求めてください。 ただし、答えは非常に大きくなることがあるので、$10^9 + 7$ で割った余りを求めてください。

注釈

ある長さ $N$ の数列 $Z$ の転倒数とは、整数 $i, j$ ( $1 \leq i < j \leq N$ ) の組であって、$Z_i > Z_j$ を満たすものの個数を意味します。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq N$ ( $1 \leq i \leq N$ )
• 入力はすべて整数である。

入力

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

$N$

$A_1$ $A_2$ $...$ $A_N$

出力

条件を満たすすべての順列の転倒数の総和を $10^9 + 7$ で割った余りを出力せよ。

3
2 3 3

4

条件を満たす順列は $(1,2,3)$, $(1,3,2)$, $(2,1,3)$, $(2,3,1)$ の $4$ つです。 それぞれの転倒数は $0$, $1$, $1$, $2$ なので、その総和である $4$ を出力します。

6
4 2 5 1 6 3

7

条件を満たす順列は $(4,2,5,1,6,3)$ のみです。 この順列の転倒数は $7$ なので、$7$ を出力します。

5
4 4 4 4 4

0

条件を満たす順列は $1$ つもありません。

30
22 30 15 20 10 29 11 29 28 11 26 10 18 28 22 5 29 16 24 24 27 10 21 30 29 19 28 27 18 23

848414012