← 返回题目列表

Codeforces · 396/D

D. 排列中倒置次数之和

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

给你一个排列 p。计算按字典顺序不超过给定排列的所有排列中的倒置总数。

由于这个数字可能非常大,因此打印它对 1000000007 (109 + 7) 取模。

输入

第一行包含一个整数 n (1 ≤ n ≤ 106) — 排列的长度。第二行包含 n 个不同的整数 p1, p2, ..., pn (1 ≤ pi ≤ n)。

输出

打印一个数字——问题的答案以 1000000007 (109 + 7) 为模。

示例

输入 #1

2
2 1

输出 #1

1

输入 #2

3
2 1 3

输出 #2

2

注意

长度为n的排列p是由n个不同的整数组成的序列,每个整数都是从1到n。

排列 p1, p2, ..., pn 的逆是一对索引 (i, j),使得 i < j 且 pi > pj。

排列 a 按字典顺序不超过排列 b,如果 a = b 或存在这样的数字 i,且满足以下逻辑条件:$$(\forall j<i,\;a_{j}=b_{j})$$ AND (ai < bi)。