给你一个排列 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)。