On Sum of Number of Inversions in Permutations

题意翻译

On Sum of Number of Inversions in Permutations （所有逆序对之和） 给你一个排列 p，计算字典序不超过 p 的所有排列里，逆序对的总个数。最后结果对 $10^9$+7 取模。 输入： 第一行一个整数 n(1≤n≤$10^6$)，表示排列元素的个数。 第二行有 n 个不同的整数 $p_1, p_2, ..., p_n (1≤p_i≤n)$，表示这个排列。 输出： 仅一个整数，表示题目中描述的所有逆序对的总个数。 说明： 排列p是指一个长度为 n 的序列，里面的元素是 1~n 的排列。 逆序对是指在序列 p 中存在两个下标(i,j)满足：i<j 而且 pi>pj。 感谢@BobHuang0724 提供的翻译

题目描述

You are given a permutation $ p $ . Calculate the total number of inversions in all permutations that lexicographically do not exceed the given one. As this number can be very large, print it modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1<=n<=10^{6} $ ) — the length of the permutation. The second line contains $ n $ distinct integers $ p_{1},p_{2},...,p_{n} $ ( $ 1<=p_{i}<=n $ ).

输出格式

Print a single number — the answer to the problem modulo $ 1000000007 $ $ (10^{9}+7) $ .

输入输出样例

输入样例 #1

2
2 1

输出样例 #1

1

输入样例 #2

3
2 1 3

输出样例 #2

2

说明

Permutation $ p $ of length $ n $ is the sequence that consists of $ n $ distinct integers, each of them is from $ 1 $ to $ n $ . An inversion of permutation $ p_{1},p_{2},...,p_{n} $ is a pair of indexes $ (i,j) $ , such that $ i&lt;j $ and $ p_{i}&gt;p_{j} $ . Permutation $ a $ do not exceed permutation $ b $ lexicographically, if either $ a=b $ or there exists such number $ i $ , for which the following logical condition fulfills:  AND $ (a_{i}&lt;b_{i}) $ .