贡献法，考虑怎么更新答案。

首先从左往右遍历，维护一个 $sum$ 即前面 $j < i$ 到当前 $i$ 的距离。此时用 $sum$ 减去当前 $i$ 相同颜色的距离。

用 $cnt_c, dis_c$ 分别维护颜色 $c$ 的数量和下标和，$ans = \sum\limits_{i=1}^n sum - (cnt_c \times i - dis_c)$ 。

#include <bits/stdc++.h>

using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

	int n;
	std::cin >> n;

	i64 sum = 0, ans = 0;
	std::vector<i64> dis(n + 1);
	std::vector<int> cnt(n + 1);
	for (int i = 0; i < n; ++i) {
		int c;
		std::cin >> c;

		ans += sum - (1LL * cnt[c] * i - dis[c]);
		dis[c] += i;
		sum += i + 1;
		cnt[c]++;
	}    

	std::cout << ans;

    return 0;
}