CF1612G Max Sum Array

给定一个数组 $c = [c_1, c_2, \dots, c_m]$。构造一个数组 $a = [a_1, a_2, \dots, a_n]$，其中 $a$ 由整数 $1, 2, \dots, m$ 组成，并且对于每个 $i \in [1, m]$，整数 $i$ 在 $a$ 中恰好出现 $c_i$ 次。因此，$a$ 的元素个数恰好为 $\sum\limits_{i=1}^{m} c_i$。 对于这样的数组 $a$，定义 $f(a)$ 为 $$ f(a) = \sum_{\substack{1 \le i < j \le n\\ a_i = a_j}}{j - i}。 $$ 换句话说，$f(a)$ 是所有相等元素对之间距离的总和。 你的任务是计算 $f(a)$ 的最大可能值，以及能达到最大值的数组 $a$ 的个数。若两个数组在某个位置上的元素不同，则认为它们是不同的。

第一行包含一个整数 $m$（$1 \le m \le 5 \times 10^5$）——数组 $c$ 的大小。 第二行包含 $m$ 个整数 $c_1, c_2, \dots, c_m$（$1 \le c_i \le 10^6$）——数组 $c$。

输出两个整数，分别表示 $f(a)$ 的最大可能值和能达到最大值的数组 $a$ 的个数。由于答案可能过大，请对 $10^9 + 7$ 取模输出。

在第一个样例中，所有可能的数组 $a$ 都是 $[1, 2, 3, 4, 5, 6]$ 的排列。由于每个数组 $a$ 都有 $f(a) = 0$，所以最大值为 $f(a) = 0$，这样的数组有 $6! = 720$ 个。 在第二个样例中，唯一可能的数组由 $10^6$ 个 $1$ 组成，其 $f(a) = \sum\limits_{1 \le i < j \le 10^6}{j - i} = 166\,666\,666\,666\,500\,000$，$166\,666\,666\,666\,500\,000 \bmod{10^9 + 7} = 499\,833\,345$。 由 ChatGPT 4.1 翻译