题目描述

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

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

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

输入格式

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

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

输出格式

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

题目大意

给定一个长度为 $n$ 的序列 $A$，问所有满足 $\forall i,P_i\le A_i$ 的 $1\sim n$ 的排列的逆序数的和为多少。

答案对 $10^9+7$ 取模。

3
2 3 3

4

6
4 2 5 1 6 3

7

5
4 4 4 4 4

0

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

提示

注釈

ある長さ $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$ )
• 入力はすべて整数である。

Sample Explanation 1

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

Sample Explanation 2

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

Sample Explanation 3

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