CF938E Max History

给定一个长度为 $n$ 的数组 $a$。我们定义 $f_{a}$ 如下： - 初始时 $f_{a}=0$，$M=1$； - 对于每个 $2 \leq i \leq n$，如果 $a_{M} < a_{i}$，则令 $f_{a}=f_{a}+a_{M}$，并将 $M=i$。 请计算数组 $a$ 的所有 $n!$ 个排列的 $f_{a}$ 之和，结果对 $10^{9}+7$ 取模。 注意：如果两个元素的下标不同，则认为它们是不同的，因此对于每个数组 $a$，恰好有 $n!$ 个排列。

第一行包含一个整数 $n$（$1 \leq n \leq 1\,000\,000$），表示数组 $a$ 的大小。 第二行包含 $n$ 个整数 $a_{1},a_{2},...,a_{n}$（$1 \leq a_{i} \leq 10^{9}$）。

输出一个整数，表示数组 $a$ 的所有 $n!$ 个排列的 $f_{a}$ 之和，对 $10^{9}+7$ 取模。

对于第二个样例，所有排列如下： - $p=[1,2,3]$：$f_{a}$ 等于 $1$； - $p=[1,3,2]$：$f_{a}$ 等于 $1$； - $p=[2,1,3]$：$f_{a}$ 等于 $1$； - $p=[2,3,1]$：$f_{a}$ 等于 $1$； - $p=[3,1,2]$：$f_{a}$ 等于 $0$； - $p=[3,2,1]$：$f_{a}$ 等于 $0$。 其中 $p$ 表示原数组 $a$ 的下标排列。$f_{a}$ 的总和为 $4$。 由 ChatGPT 4.1 翻译