1888C - You Are So Beautiful - CodeForces Solution

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
using namespace std;
#define ll long long
#define db double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<db, db>
#define iter set<int>::iterator
#define lter set<ll>::iterator
#define vct vector
#define str string
#define mset multiset
#define umap unordered_map
#define fo(i, l, r) for (int i = l; i <= r; i++)
#define of(i, l, r) for (int i = l; i >= r; i--)
#define inl inline
#define fi first
#define se second
#define in insert
#define er erase
#define ct count
#define pb push_back
#define pf push_front
#define lowb lower_bound
#define upb upper_bound
#define sz size()
#define cl clear()
#define em empty()
#define be begin()
#define en end()
#define fr front()
#define bk back()
#define ppb pop_back()
#define ppf pop_front()
#define S s = " " + s
#define SS s[i] = " " + s[i]
#define all(g) g.be, g.en
#define lbt(x) ((x) & (-x))
#define mem(a, x) memset(a, x, sizeof(a))
#define sp(x) fixed << setprecision(x)
#define M(x) x %= mod, x += mod, x %= mod
#define ANS cout << ans << '\n'
#define YES cout << "YES\n"
#define Yes cout << "Yes\n"
#define NO cout << "NO\n"
#define No cout << "No\n"
#define print(x) cout << #x << '=' << x << '\n';
#define printt(x, y) cout << #x << '=' << x << ',' << #y << '=' << y << '\n';
#define ied " \n"[i == n]
#define jed " \n"[j == n]
#define ked " \n"[k == n]
#define GG g[u].pb(v), g[v].pb(u)
const db pi = acos (-1.0);
// int mod = 998244353;
// int modd = 1e9 + 7;
const int mod = 998244353;
const int modd = 1e9 + 7;
// ax+by=gcd
// x=x0+b/gcd*k
// y=y0+a/gcd*k
inl ll exgcd (ll a, ll &x, ll b, ll &y)
{
	if (b == 0)
	{
		x = 1, y = 0;
		return a;
	}
	ll tt = exgcd (b, y, a % b, x);
	y -= a / b * x;
	return tt;
}
inl ll gcd (ll a, ll b)
{
	if (b == 0)
		return a;
	return gcd (b, a % b);
}
ll qp (ll a, ll b)
{
	ll s = 1;
	while (b > 0)
	{
		if (b & 1)
			s = (s * a) % mod;
		b >>= 1, a = (a * a) % mod;
	}
	return s;
}
ll ny (ll a)
{
	// ll x, y;
	// if (exgcd(a, x, mod, y) == 1)
	//     return (x % mod + mod) % mod;
	// else
	//     return -1;
	return qp (a, mod - 2);
}
// const int X = 1e6 + 5;
// ll fc[X], nn[X], NN[X];
// void CC()
// {
//     fc[0] = nn[0] = NN[0] = 1;
//     fo(i, 1, X - 2) fc[i] = fc[i - 1] * i % mod;
//     NN[X - 2] = ny(fc[X - 2]);
//     of(i, X - 2 - 1, 1) NN[i] = NN[i + 1] * (i + 1) % mod;
//     fo(i, 1, X - 2) nn[i] = NN[i] * fc[i - 1] % mod;
// }
// ll C(int n, int m)
// {
//     if (n < m || n < 0 || m < 0)
//         return 0;
//     return fc[n] * NN[m] % mod * NN[n - m] % mod;
// }
int dx[5] = {0, 1, 0, -1, 0};
int dy[5] = {0, 0, 1, 0, -1};
ll MAX = 0x3f3f3f3f3f3f3f3fll;
ll MIN = -MAX;
ll t, n, m, k, x, y, z, u, v, w, l, r, mid;
ll tt, qq, ff, ok, T;
ll mx, mi, op, pos, len, sum, ans;

void CL()
{
	ans = sum = ff = tt = ok = mx = x = y = z = n = m = k = 0, mi = MAX;
	return;
}
const int N = 1e6 + 5;
ll a[N];
ll b[N], c[N];
ll f[N], vis[N];
str s, ss;
// vct<int> g[N];

void solve()
{
	cin >> n;
	fo (i, 1, n)
	{
		cin >> a[i];
	}
	map<ll, ll>ma, mb;

	of (i, n, 1)
	{
		if (!mb.ct (a[i]) )
		{
			y++;
		}
		mb[a[i]]++;
	}
	fo (i, 1, n)
	{
		if (ma.ct (a[i]) )
		{
			mb[a[i]]--;
			if (mb[a[i]] == 0)
			{
				y--;
			}
			continue;
		}
		ans += y;
		ma[a[i]] = 1;
		mb[a[i]]--;
		if (mb[a[i]] == 0)
		{
			y--;
		}
	}
	ANS;
	return;
}

int main()
{
	// CC();
	// Euler();
	ios::sync_with_stdio (0), cin.tie (0), cout.tie (0);
	cin >> T; while (T--)
	{
		CL();
		solve();
	}
	return 0;
}