题目描述

すぬけ君有一个长度为 $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$ 取模后的结果。

样例 1

输入

3
2 3 3

输出

4

样例 2

输入

6
4 2 5 1 6 3

输出

7

样例 3

输入

5
4 4 4 4 4

输出

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

输出

848414012

说明/提示

注释

一个长度为 $N$ 的数列 $Z$ 的逆序数是指满足 $Z_i > Z_j$ 的整数对 $(i, j)$（$1 \leq i < j \leq N$）的个数。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq N$（$1 \leq i \leq N$）
• 输入均为整数。

样例解释 1

满足条件的排列有 $(1,2,3)$、$(1,3,2)$、$(2,1,3)$、$(2,3,1)$ 共 $4$ 个。它们的逆序数分别为 $0$、$1$、$1$、$2$，因此总和为 $4$，输出 $4$。

样例解释 2

满足条件的排列只有 $(4,2,5,1,6,3)$。该排列的逆序数为 $7$，因此输出 $7$。

样例解释 3

没有任何满足条件的排列。

由 ChatGPT 4.1 翻译