AT_kupc2018_e.転倒数

给定一个长度为 $N$ 的排列 $P = p_1, p_2, \ldots, p_N$。请你求出所有长度为 $N$ 的排列中，字典序小于等于 $P$ 的所有排列的逆序数之和。由于答案可能非常大，请输出其对 $10^9 + 7$ 取模后的结果。

其中，排列 $X = x_1, x_2, \ldots, x_N$ 的逆序数定义为满足 $1 \leq i < j \leq N$ 且 $x_i > x_j$ 的整数对 $(i, j)$ 的个数。

输入从标准输入中给出，格式如下：

$N$ $p_1$ $p_2$ $\ldots$ $p_N$

请输出所有长度为 $N$ 的排列中，字典序小于等于排列 $P$ 的所有排列的逆序数之和，对 $10^9 + 7$ 取模后的结果。

限制条件

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

样例解释 1

字典序小于等于排列 $(2, 1, 3)$ 的长度为 $3$ 的排列有 $(1, 2, 3)$、$(1, 3, 2)$、$(2, 1, 3)$ 共 $3$ 种。这些排列的逆序数分别为 $0, 1, 1$，因此答案为 $0 + 1 + 1 = 2$。

由 ChatGPT 4.1 翻译