首先，我们可以将给定的数字映射到 $[1, 10^6]$ 范围内的整数。设 $l_i = f(1, i, a_i)$，$r_i = f(i, n, a_i)$，我们想要找到满足 $i < j$ 且 $l_i > r_j$ 的数对 $(i, j)$ 的数量。

为了计算 $l_i$，我们可以维护一个名为 $cnt$ 的数组，用来记录每个值出现的次数。具体做法是：从左到右遍历数组，并更新 $cnt$ 数组；在位置 $i$ 处，$l_i$ 就等于 $cnt[a_i]$ 的值（$r_i$ 可以用类似的方法计算）。

除此之外，我们还可以借助树状数组（Fenwick Tree）来解决。我们使用一个树状数组，并从右到左遍历。在每一步中，我们将树状数组中小于 $l_i$ 的元素个数累加到答案中，然后将 $r_i$ 加入到树状数组里。

总时间复杂度：$O(n \log n)$。

此外，我们也可以使用分治法（divide and conquer）来解决这个问题。你可以参考第二个示例解法来了解具体的实现方式。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1000 * 1000 + 10;

int fen[MAXN];

void add(int x, int val)
{
    for (int i = x + 1; i < MAXN; i += i & (-i)) fen[i] += val;
}

int get(int x)
{
    int ans = 0;
    for (int i = x; i > 0; i -= i & (-i)) ans += fen[i];
    return ans;
}

int sum(int x, int y)
{
    return get(y) - get(x);
}

int rem[MAXN], cnt[MAXN], a[MAXN], tot[MAXN], sz;

int main()
{
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    for (int i = 0; i < n; i ++) cin >> a[i], tot[sz++] = a[i];

    sort(tot, tot + sz);
    sz = unique(tot, tot + sz) - tot;

    for (int i = 0; i < n; i ++) a[i] = lower_bound(tot, tot + sz, a[i]) - tot;

    for (int i = n - 1; i >= 0; i --)
    {
        cnt[a[i]] ++;
        add(cnt[a[i]], 1);

        rem[i] = cnt[a[i]];
    }

    memset(cnt, 0, sizeof cnt);
    long long ans = 0;
    for (int i = 0; i < n; i ++)
    {
        add(rem[i], -1);
        
        cnt[a[i]] ++;
        ans += sum(1, cnt[a[i]]);
    }

    cout << ans << endl;
    return 0;
}