Untitled

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);
	vector<vector<int>> occ(n + 1);
	map<int,int> freq;
	int ans = 0;
	BIT<int> bit(n + 10);
	for(int i = 1; i <= n; ++i){
		cin >> ar[i];
		freq[ar[i]]++;
		occ[ar[i]].push_back(i);
		ans += (int)freq.size();
		bit.upd(i, freq.size());
	}

	for(int i = 2; i <= n; ++i){
		int x = ar[i - 1];
		if(freq[x] == 1){
			bit.upd(i, n, -1); // it should update i to n with -1 right?
		}
		else{
			int idx = *lower_bound(all(occ[x]), i);
			if(idx != i){
				bit.upd(i, idx, -1); // same range updation?
			}
		}
		ans += bit.query(i, n); // i want sum from i to n
		freq[x]--;
	}
	cout << ans << endl;
}