Let us perform in linear time the final part of the official editorial where we count the number of pairs \((i, j)\) \((i < j)\) such that \(A_i + A_j \geq 10^8\). Below, let \(M \coloneqq 10^8\).

First, declare an array \(\text{cnt}\) of length \(M\), and store in \(\text{cnt}[i]\) the count of values among \(A_1, \ldots, A_N\) that are at most \(i\). This can be done in \(O(N + M)\) time. Please see the sample implementation for the specific procedure.

Next, for each \(A_i\), calculate the count of values among \(A_1, \ldots, A_N\) (excluding \(A_i\) itself) that are at least \(M - A_i\). If we ignore the “excluding \(A_i\)” part, this is \(N - \text{cnt}[M - A_i - 1]\). However, if \(2A_i \geq M\), then \(A_i\) itself is included here, so we subtract \(1\).

Summing up these \(N\) counts yields the number of pairs \((i, j)\) \((i \neq j)\) such that \(A_i + A_j \geq M\). Divide this by \(2\) to get the desired count of pairs \((i, j)\) \((i < j)\).

Sample Implementation (Python):

N = int(input())
A = list(map(int, input().split()))
M = 10**8

cnt = [0] * (M + 1)
for a in A:
    cnt[a] += 1
for i in range(M):
    cnt[i + 1] += cnt[i]

p = 0
for a in A:
    p += N - cnt[M - a - 1]
    if 2 * a >= M:
        p -= 1
print((N - 1) * sum(A) - p // 2 * M)