配点 : 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