公式解説の最後の \(A_i + A_j \geq 10^8\) であるようなペア \((i, j)\) \((i < j)\) を数える部分を線形時間で行います。以下、\(M \coloneqq 10^8\) とします。

まず、長さ \(M\) の配列 \(\text{cnt}\) を宣言し、\(\text{cnt}[i]\) に \(A_1, \ldots, A_N\) のうち \(i\) 以下の値の個数を格納します。これは \(O(N + M)\) 時間で可能です。具体的な手順は実装例を見てください。

次に、各 \(A_i\) について、\(A_1, \ldots, A_N\) のうち \(A_i\) 以外で \(M - A_i\) 以上であるものの個数を求めます。これは、「\(A_i\) 以外」という部分を無視すれば \(N - \text{cnt}[M - a - 1]\) です。ただし、\(2 A_i \geq M\) の場合は \(A_i\) 自身が含まれてしまうため、\(1\) を引きます。

こうして求めた \(N\) 個の個数を合計すると、\(A_i + A_j \geq M\) であるようなペア \((i, j)\) \((i \neq j)\) の個数となります。これを \(2\) で割ったものが求めたいペア \((i, j)\) \((i < j)\) の個数です。

実装例：（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)