题目描述

Snuke 有一个整数序列 $A$，其长度为 $N$。他喜欢满足以下条件的置换 $(1, 2, ..., N)$，$P$：

• 对于所有 $i$（$1 \leq i \leq N$），有 $P_i \leq A_i$。

Snuke 对满足这个条件的置换的逆序数很感兴趣。求满足条件的所有置换的逆序数之和。由于结果可能非常大，计算结果模 $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$

输出格式

输出满足条件的所有置换的逆序数之和。

示例输入 1

3
2 3 3

示例输出 1

4

有四个满足条件的置换：$(1,2,3)$，$(1,3,2)$，$(2,1,3)$ 和 $(2,3,1)$。这些置换的逆序数分别为 $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

没有满足条件的置换。

示例输入 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