Max Sum Array
Contest: Educational Codeforces Round 117 (Rated for Div. 2)
Difficulty rating: 2500
Tags: combinatorics, constructive algorithms, greedy, sortings

You are given an array $$$c = [c_1, c_2, \dots, c_m]$$$. An array $$$a = [a_1, a_2, \dots, a_n]$$$ is constructed in such a way that it consists of integers $$$1, 2, \dots, m$$$, and for each $$$i \in [1,m]$$$, there are exactly $$$c_i$$$ occurrences of integer $$$i$$$ in $$$a$$$. So, the number of elements in $$$a$$$ is exactly $$$\sum\limits_{i=1}^{m} c_i$$$.

Let's define for such array $$$a$$$ the value $$$f(a)$$$ as $$$$$$f(a) = \sum_{\substack{1 \le i < j \le n\\ a_i = a_j}}{j - i}.$$$$$$

In other words, $$$f(a)$$$ is the total sum of distances between all pairs of equal elements.

Your task is to calculate the maximum possible value of $$$f(a)$$$ and the number of arrays yielding the maximum possible value of $$$f(a)$$$. Two arrays are considered different, if elements at some position differ.

Input format:
The first line contains a single integer $$$m$$$ ($$$1 \le m \le 5 \cdot 10^5$$$) — the size of the array $$$c$$$.

The second line contains $$$m$$$ integers $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_i \le 10^6$$$) — the array $$$c$$$.

Output format:
Print two integers — the maximum possible value of $$$f(a)$$$ and the number of arrays $$$a$$$ with such value. Since both answers may be too large, print them modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, all possible arrays $$$a$$$ are permutations of $$$[1, 2, 3, 4, 5, 6]$$$. Since each array $$$a$$$ will have $$$f(a) = 0$$$, so maximum value is $$$f(a) = 0$$$ and there are $$$6! = 720$$$ such arrays.

In the second example, the only possible array consists of $$$10^6$$$ ones and its $$$f(a) = \sum\limits_{1 \le i < j \le 10^6}{j - i} = 166\,666\,666\,666\,500\,000$$$ and $$$166\,666\,666\,666\,500\,000 \bmod{10^9 + 7} = 499\,833\,345$$$.

Example input:
6
1 1 1 1 1 1

Example output:
0 720

Example input:
1
1000000

Example output:
499833345 1

Editorial:
Firstly, let's prove that at first and last positions of $$$a$$$ the most frequent elements should be placed (but not necessary the same). WLOG, let's prove that $$$c_{a_1} \ge c_{a_i}$$$ for any $$$i > 1$$$.
By contradiction, let's $$$p$$$ be the smallest index such that $$$c_{a_1} < c_{a_p}$$$. What happens if we swap them? Since $$$p$$$ is the first such index then there are no $$$a_i = a_p$$$ for $$$i < p$$$, so "contribution" of $$$a_p$$$ will increase by exactly $$$inc = (c_{a_p} - 1) \cdot (p - 1)$$$. From the other side, contribution of $$$a_1$$$ consists of two parts: pairs with elements from $$$(p, n]$$$ and from $$$(1, p)$$$. For all elements from $$$(p, n]$$$ decrease will be equal to $$$dec_1 = c_{a_1}[p + 1, n] \cdot (p - 1)$$$ and from elements in $$$(1, p)$$$ $$$dec_2 \le c_{a_1}[2, p - 1] \cdot (p - 1)$$$.
So, the total decrease $$$dec$$$ after moving $$$a_1$$$ to position $$$p$$$ equal to $$$dec = dec_1 + dec_2 \le (c_{a_1} - 1) \cdot (p - 1)$$$. The total difference in such case is equal to $$$inc - dec \ge (p - 1) \cdot (c_{a_p} - c_{a_1}) > 0$$$. So, our placement is not optimal — contradiction.
Let's suggest that there is exactly one $$$e$$$ with maximum $$$c_{e}$$$. According to what we proved earlier, both $$$a_1$$$ and $$$a_n$$$ must be equal to $$$e$$$. Contribution of the first and last elements will be equal to: $$$(n - 1)$$$ for pair $$$(1, n)$$$ and for each element $$$i$$$ ($$$1 < i < n$$$) with $$$a_i = e$$$ we add $$$(i - 1) + (n - i) = (n - 1)$$$ for pairs $$$(1, i)$$$ and $$$(i, n)$$$. So, the total contribution of $$$a_1 = a_n = e$$$ is equal to $$$(n - 1) \cdot (c_e - 1)$$$.
Note that this contribution is independent of positions of other $$$e$$$ in the array $$$a$$$, so that's why we can cut first and last elements of $$$a$$$ and solve the task recursively.
Unfortunately, in the initial task we may have several $$$e_1, e_2, \dots, e_k$$$ with maximum $$$c_{e_i}$$$. But we in the similar manner can prove that the first (and last) $$$k$$$ elements $$$a_1, \dots, a_k$$$ should be some permutation of $$$e_1, \dots e_k$$$. Now, let's prove that any permutation of first and last $$$k$$$ elements is optimal.
Suppose, positions of $$$e_i$$$ are $$$l_i$$$ ($$$1 \le l_i \le k$$$) and $$$r_i$$$ ($$$n - k + 1 \le r_i \le n$$$). Then the contribution of $$$e_i$$$ is equal to $$$(c_{e_i} - 1) \cdot (r_i - l_i)$$$. The total contribution of all $$$e_i$$$ is $$$\sum\limits_{i=1}^{k}{(c_{e_i} - 1) \cdot (r_i - l_i)}$$$ $$$=$$$ $$$(c_{e_1} - 1) (\sum\limits_{i=1}^{k}r_i - \sum\limits_{i=1}^{k}{l_i})$$$ $$$=$$$ $$$(c_{e_1} - 1)((n - k)k + \frac{k(k + 1)}{2} - \frac{k(k+1)}{2}) = (c_{e_1} - 1) k (n - k)$$$. This contribution doesn't depend on chosen $$$l_i$$$ and $$$r_i$$$, so any permutation of first $$$k$$$ elements and any permutation of last $$$k$$$ elements give optimal answer.
As a result, the algorithm is following:
• Find all maximums $$$e_1, \dots, e_k$$$ in $$$c$$$.
• If $$$c_{e_1} = 1$$$ then any permutation of remaining elements has $$$f(a) = 0$$$ (there are $$$k!$$$ such permutations).
• Otherwise, add $$$(c_{e_1} - 1) k (n - k)$$$ to the total balance, and multiply the number of variants by $$$(k!)^2$$$.
• Cut prefix and suffix by making $$$c_{e_i} = c_{e_i} - 2$$$ for each $$$e_i$$$ (obviously, $$$n = n - 2k$$$) and repeat the whole process.
We can implement the algorithm fast if we keep the number of $$$c_i$$$ equal to each $$$val$$$ from $$$0$$$ to $$$C$$$ ($$$C \le 10^6$$$). So the total complexity is $$$O(n + C)$$$.