Можно решить ДО.

Посчитай массив cntback[i], количество чисел от i до n, таких, что они равны a[i]. Это можно сделать так:

for(int i = n; i >= 1; --i)
   Cnt[a[i]]++, cntback[i] = Cnt[a[i]];

Теперь, ты просто пробегаешься циклом от 1 до n, и считаешь вхождение каждого числа от 1 до i. Это можно сделать так:

for(int i = 1; i <= n; ++i) {
    cnt[a[i]]++;
    curcnt = cnt[a[i]];
    ans += количество cntback от i + 1 до n, которые больше чем curcnt
}

Теперь, как посчитать это количество? ДО.

Когда считаем cntback, сразу обновляем его в ДО:

for(int i = n; i >= 1; --i)
   Cnt[a[i]]++, cntback[i] = Cnt[a[i]], upd(1, 1, n, cntback[i], 1);

Это значит, что мы обновляем элемент в дереве с индексом cntback[i], увеличиваем его на 1.

Теперь, подсчет выглядит так:

for(int i = 1; i <= n; ++i) {
    upd(1, 1, n, cntback[i], -1); // нам нужно от i + 1, i + 2, i - тый больше не считаем, отнимаем его
    cnt[a[i]]++;
    curcnt = cnt[a[i]];
    ans += get(1, 1, n, 1, curcnt - 1); // get(v, tl, tr, l, r) - возвращает сумму от l до r
}