分数: 1700 点
问题陈述
Snuke 有一个整数序列 A 其长度为 N。 他喜欢排列 (1, 2, ..., N), P,满足以下条件:
- P_i \leq A_i 对于所有人 i ( 1 \leq i \leq N ).
Snuke 对这种排列的反转数感兴趣。 求满足条件的所有排列的反转数之和。 由于这可能非常大,因此计算总和模 10^9+7.
注释
的 反转数 序列的 一个序列的 Z 其长度 N 是整数对的数量 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