https://codeforces.com/contest/1969/problem/E
好吧主要是思维。
题意：定义一个数组a时唯一的：a中存在一个元素，它只在a中出现一次。
定义一个操作：将任意一个元素修改为任意一个数。
求把a的所有连续子数组都变为唯一的最小操作数。即任意一个子数组都有一个元素，它在该连续子数组中只出现一次。

1.如果一定要修改某个元素，直接把它修改为数组中不存在的某个数。这样跨过该位置的连续子数组一定是唯一的。因此可以从前往后遍历数组，找到一个必须修改的位置st后，st以前的数就不需要考虑了。因此可以贪心一下，答案一定是，从前往后遍历数组，一直找到第一个“必须修改的位置”，修改，然后继续遍历。一直重复这个操作直到遍历完。
2.考虑如何找到st。如果一个数组一定要修改元素，那么一定有：每个元素都至少出现两次。如果当一个元素出现只一次时，我们可以维护一个初始为0的数组，从后往前观察这个数组，如果某个元素是第一次出现，那么[st,idx1]这个位置可以++，如果这个元素是第二次出现那么[st,idx2]这个位置应该–(即代表[idx2+1,idx1]这个区间为1，代表存在该元素是只出现一次)，之后再出现出现则不需要关注。这样如果[st,i]区间的有数为0，就代表[st,pos]这个区间内，所有元素没有只出现一次的元素。
想到这个点的话，发现只需要区间加、和区间最小值两个操作，用线段树维护即可。
3.综上，当遍历到i位置时，修改a[i]元素相关信息：即[st,idx1]要加一，此外，需要[st,idx2]减一，但是注意当我们在之前遍历的时候[st,idx2]这个位置加过一，现在要修改为减一，所以应该减二。至于第三次出现，在上次遍历到idx2的时候是减一，而此时这个减一应该修改为0，所以[st,idx3]要加一。
修改之后查询st到idx1的最小值，如果最小值为0，说明idx1位置必须修改。则操作次数加一，并设置st为i+1

#include<bits/stdc++.h>

#define MULTI_TEST

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
struct SegmentTree {
    int n;
    vector<int> tag;
    vector<int> val;
    SegmentTree(int n_):n(n_),tag(4*n_),val(4*n_){}
    void pushup(int p){
        val[p] = min(val[2*p],val[2*p+1]);
    }
    void pushdown(int p){
        tag[2*p] += tag[p];
        tag[2*p+1] += tag[p];
        val[2*p] += tag[p];
        val[2*p+1] += tag[p];
        tag[p] = 0;
    }
    void modify(int u,int l,int r,int L,int R,int v){
        if(L>R) return;
        if(L<=l&&r<=R){
            tag[u] += v; val[u] += v;
            return;
        }
        int mid = (l+r)>>1;
        pushdown(u);
        if(L<=mid) modify(2*u,l,mid,L,R,v);
        if(R>mid) modify(2*u+1,mid+1,r,L,R,v);
        pushup(u);
    }
    int query(int u,int l,int r,int L,int R){
        if(L>R) return 1e9;
        if(L<=l&&r<=R){
            return val[u];
        }
        pushdown(u);
        int mid  = (l+r)>>1;
        int res = 1e9;
        if(L<=mid) res= min(res,query(2*u,l,mid,L,R));
        if(R>mid) res= min(res,query(2*u+1,mid+1,r,L,R));
        return res;
    }
};
void solve(){
    int n;cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    SegmentTree seg(n+1);
    vector<vector<int>> pos(n+1);
    int ans = 0,st = 1 ;
    for(int i=1;i<=n;i++){
        int x = a[i];
        pos[x].push_back(i);
        int k = pos[x].size();
        if(k>0) seg.modify(1,1,n,st,pos[x][k-1],1);
        if(k>1) seg.modify(1,1,n,st,pos[x][k-2],-2);
        if(k>2) seg.modify(1,1,n,st,pos[x][k-3],1);
        int res = seg.query(1,1,n,st,i);
        if(res==0) ans++,st = i+1;
    }
    cout<<ans<<endl;
}

int main(){     
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}