1612G - Max Sum Array - CodeForces Solution

import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

m = int(input())
mod = pow(10, 9) + 7
c = list(map(int, input().split()))
n = pow(10, 6) + 5
fact = [1] * (n + 1)
for i in range(1, n + 1):
    fact[i] = i * fact[i - 1] % mod
cnt = [0] * (n + 1)
for i in c:
    cnt[i - 1] += 1
for i in range(n - 2, -1, -1):
    cnt[i] += cnt[i + 2]
s, c, u = 0, 1, 0
inv2 = pow(2, mod - 2, mod)
y = 0
for i in range(-n, n):
    j = abs(i)
    if not cnt[j]:
        continue
    u += cnt[j]
    u %= mod
    x = u * (u + 1) % mod
    s += i * (x - y) % mod
    s %= mod
    y = x
    c *= fact[cnt[j]]
    c %= mod
s = s * inv2 % mod
print(s, c)