三、完善程序（单选题，每小题 3 分，共计 30 分）

程序（1）：序列问题

给定序列 $a_n$，求有多少对 $(i,j)$ 满足 $a_i<a_j$。数据满足 $n \le 10^6$，$a_i \le 10^9$。

提示：对于任意 $a_i \ne a_j$，$(i,j)$ 或 $(j,i)$ 能对答案产生 1 的贡献，因此可以用总对数减去 $a_i=a_j$ 的 $(i,j)$ 数量。试补全程序。

#include <bits/stdc++.h>
using namespace std;

const int Maxn = ①;
int n, a[Maxn];
long long s[Maxn], ans;

bool check(int l, int r) {
    if (s[r] - s[l - 1] == ②) return true;
    return false;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        s[i] = s[i - 1] + a[i];
    ans = ③;
    for (int i = 1; i <= n;) {
        int l = i, r = n, pos = n;
        while (④) {
            int mid = (l + r) >> 1;
            if (check(l, mid))
                l = mid + 1, pos = mid;
            else
                r = mid - 1;
        }
        ans -= ⑤;
        i = pos + 1;
    }
    cout << ans;
}

1. ② 处应填（ ）。

{{ select(1) }}

• (r - l + 1) * a[l]
• s[r] - s[l - 1]
• 1LL * (r - l + 1) * a[l]
• a[1] = 0