← 返回题目列表

AtCoder · agc023_e

E. 反转

中文机器翻译题面 查看原题

分数: 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