Untitled

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

template <class T> struct BIT { //1-indexed
  int n; vector<T> t;
  BIT() {}
  BIT(int _n) {
    n = _n; t.assign(n + 1, 0);
  }
  T query(int i) {
    T ans = 0;
    for (; i >= 1; i -= (i & -i)) ans += t[i];
    return ans;
  }
  void upd(int i, T val) {
    if (i <= 0) return;
    for (; i <= n; i += (i & -i)) t[i] += val;
  }
  void upd(int l, int r, T val) {
    upd(l, val);
    upd(r + 1, -val);
  }
  T query(int l, int r) {
    return query(r) - query(l - 1);
  }
};
void dxt(){
	int n; cin >> n;
	vector<int> ar(n + 1), freq(n + 1);
	vector<vector<int>> occ(n + 1);
	set<int> st; int ans = 0;
	BIT<int> bit(n + 10);
	for(int i = 1; i <= n; ++i){
		cin >> ar[i];
		st.insert(ar[i]);
		ans += st.size();
		freq[i] = st.size();
		bit.upd(i, freq[i]);
		occ[ar[i]].push_back(i);
	}
	for(int i = 1; i <= n; ++i){
		if(occ[i].size()){
			if(occ[i].back() != n){
				occ[i].push_back(n);
			}
		}
	}
	debug(occ);
	auto search = [&](int idx, int key){
		int low = 0, high = occ[idx].size() - 1, ans;
		while(low <= high){
			int mid = (low + high)/2;
			if(occ[idx][mid] <= key){
				low = mid + 1;
			}
			else{
				ans = mid;
				high = mid - 1;
			}
		}
		return ans;
	};
	for(int i = 2; i <= n; ++i){
		int x = ar[i - 1];
		int idx = search(x, i - 1);
		debug(bit.query(i, n));
		bit.upd(i, occ[x][idx], -1);
		debug(bit.query(i, n));
		int t = bit.query(i, n);
		debug(x, occ[x][idx]);
	}
	cout << ans << endl;
}

int main(){
    int T = 1;
    cin >> T;
    while(T--){
        dxt();
    }
}
    }
}