E - Inversions Editorial /

Time Limit: 3 sec / Memory Limit: 256 MB

配点 : 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 で割った余りを出力せよ。

入力例 1

3
2 3 3

出力例 1

4

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

入力例 2

6
4 2 5 1 6 3

出力例 2

7

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

入力例 3

5
4 4 4 4 4

出力例 3

0

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

入力例 4

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

出力例 4

848414012

Score : 1700 points

Problem Statement

Snuke has an integer sequence A whose length is N. He likes permutations of (1, 2, ..., N), P, that satisfy the following condition:

  • P_i \leq A_i for all i ( 1 \leq i \leq N ).

Snuke is interested in the inversion numbers of such permutations. Find the sum of the inversion numbers over all permutations that satisfy the condition. Since this can be extremely large, compute the sum modulo 10^9+7.

Notes

The inversion number of a sequence Z whose length N is the number of pairs of integers i and j ( 1 \leq i < j \leq N ) such that Z_i > Z_j.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq N ( 1 \leq i \leq N )
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the sum of the inversion numbers over all permutations that satisfy the condition.

Sample Input 1

3
2 3 3

Sample Output 1

4

There are four permutations that satisfy the condition: (1,2,3), (1,3,2), (2,1,3) and (2,3,1). The inversion numbers of these permutations are 0, 1, 1 and 2, respectively, for a total of 4.

Sample Input 2

6
4 2 5 1 6 3

Sample Output 2

7

Only one permutation (4,2,5,1,6,3) satisfies the condition. The inversion number of this permutation is 7, so the answer is 7.

Sample Input 3

5
4 4 4 4 4

Sample Output 3

0

No permutation satisfies the condition.

Sample Input 4

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

Sample Output 4

848414012