← 返回题目列表

AtCoder · kupc2018_e

E. 跌倒次数

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

配点 : 200 点

問題文

长度 小于或等于 N 的排列 给出了 P = p_1, p_2, ..., p_N 。长度 N 的排列,P 查找所有字典顺序较小或相等的数字的翻转次数,并计算总和。然而,答案可能非常大,所以 请输出除以10^9 + 7 后的余数。

然而,排列 X = x_1, x_2, ..., x_N 跌倒的次数是多少? 满足1 \leq i < j \leq N 和 x_i > x_j 的整数 选择 i, j 的对数。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq p_i \leq N
  • 所有输入均为整数。
  • p_1, p_2, ..., p_N 是一个排列。

入力

输入是按以下格式从标准输入给出的。

N
p_1 p_2 ... p_N

出力

长度 小于或等于 N 的排列,排列 P 查找字典顺序上彼此较小或相等的所有项目的跌倒次数,并计算次数之和。 10^9 + 7 除以后的余数输出。


入力例1

3
2 1 3

出力例1

2

順列 (2, 1, 3) 按字典顺序小于或等于长度 3 的排列是 (1, 2, 3), (1, 3, 2), (2, 1, 3) 可以得到第 3 类型。

每个排列的跌倒次数为 0, 1, 1 所以答案是 0 + 1 + 1 = 2 。 对于


入力例2

4
1 2 3 4

出力例2

0

入力例3

8
5 6 2 7 1 3 8 4

出力例3

281881