#include "unique.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#define MAXN 100000
using namespace std;

struct dynamic_segment_tree  {
    struct node {
        int lind,rind;
        int sum;
        node () : lind(0), rind(0), sum(0) {
        }
    };
    vector <node> nodes;
    dynamic_segment_tree () {
        nodes.push_back(node());
    }
    void build (int ind, int l, int r, vector <int>& vals, int from, int to) {
        nodes[ind].sum=to-from+1;
        if (l==r) return ;
        int mid=l+(r-l)/2; /// for negative numbers
        int pos=from-1;
        for (int i=from; i<=to; i++) {
            if (vals[i]>mid) break;
            pos=i;
        }
        if (from<=pos) {
            if (nodes[ind].lind==0) {
                nodes[ind].lind=nodes.size();
                nodes.push_back(node());
            }
            build(nodes[ind].lind,l,mid,vals,from,pos);
        }
        if (pos+1<=to) {
            if (nodes[ind].rind==0) {
                nodes[ind].rind=nodes.size();
                nodes.push_back(node());
            }
            build(nodes[ind].rind,mid+1,r,vals,pos+1,to);
        }
    }
    void update (int ind, int l, int r, int pos, int val) {
        nodes[ind].sum+=val;
        if (l==r) return ;
        int mid=l+(r-l)/2; /// for negative numbers
        if (pos<=mid) {
            if (nodes[ind].lind==0) {
                nodes[ind].lind=nodes.size();
                nodes.push_back(node());
            }
            update(nodes[ind].lind,l,mid,pos,val);
        }
        else {
            if (nodes[ind].rind==0) {
                nodes[ind].rind=nodes.size();
                nodes.push_back(node());
            }
            update(nodes[ind].rind,mid+1,r,pos,val);
        }
    }
    int query (int ind, int l, int r, int ql, int qr) {
        if ((ql<=l)&&(r<=qr)) return nodes[ind].sum;
        int mid=l+(r-l)/2; /// for negative numbers
        int ans=0;
        if ((ql<=mid)&&(nodes[ind].lind!=0)) ans+=query(nodes[ind].lind,l,mid,ql,qr);
        if ((qr>mid)&&(nodes[ind].rind!=0)) ans+=query(nodes[ind].rind,mid+1,r,ql,qr);
        return ans;
    }
};

dynamic_segment_tree segs0;
int n;
int tmp[MAXN+2];
struct tree2d {
    dynamic_segment_tree nodes[4*(MAXN+2)];
    bool segs;
    void build (int ind, int l, int r, vector <int>& init) {
        if (l==r) {
            if (init[l]!=-1e9) nodes[ind].update(0,-1,n+1,init[l],+1);
            return;
        }
        int mid=(l+r)/2;
        build(2*ind+1,l,mid,init);
        build(2*ind+2,mid+1,r,init);
        merge(init.begin()+l,init.begin()+mid+1,init.begin()+mid+1,init.begin()+r+1,tmp+l);
        int st=l;
        for (int i=l; i<=r; i++) {
            init[i]=tmp[i];
            if (init[i]==-1e9) st++;
        }
        nodes[ind].build(0,-1,n+1,init,st,r);
    }
    int query (int ind, int l, int r, int ql, int qr, int from, int to) {
        if ((ql<=l)&&(r<=qr)) {
            int ans=0;
            if ((segs==true)&&(l==0)) ans+=segs0.query(0,-1,n+1,from,to);
            ans+=nodes[ind].query(0,-1,n+1,from,to);
            return ans;
        }
        int mid=(l+r)/2;
        int ans=0;
        if (ql<=mid) ans+=query(2*ind+1,l,mid,ql,qr,from,to);
        if (qr>mid) ans+=query(2*ind+2,mid+1,r,ql,qr,from,to);
        return ans;
    }
    void update (int ind, int l, int r, int pos, int old, int new1) {
        if ((segs==true)&&(pos==0)) {
            segs0.update(0,-1,n+1,old,-1);
            segs0.update(0,-1,n+1,new1,+1);
            return ;
        }
        nodes[ind].update(0,-1,n+1,old,-1);
        nodes[ind].update(0,-1,n+1,new1,+1);
        if (l==r) return ;
        int mid=(l+r)/2;
        if (pos<=mid) update(2*ind+1,l,mid,pos,old,new1);
        else update(2*ind+2,mid+1,r,pos,old,new1);
    }
};
tree2d segs,prev1;

multiset <int> inds[MAXN+1];
vector <int> a;
void init (vector <int> a) {
    n=a.size();
    a.insert(a.begin(),-1);
    ::a=a;
    for (int val=1; val<=n; val++) {
        inds[val].insert(-1);
        inds[val].insert(-1);
        inds[val].insert(n+2);
        inds[val].insert(n+2);
    }
    for (int i=1; i<=n; i++) {
        int val=a[i];
        inds[val].insert(i);
    }
    vector <int> tmp(n+2,-1e9),tmp2(n+2);
    for (int val=1; val<=n; val++) {
        for (auto it=inds[val].begin(); it!=inds[val].end(); it++) {
            if ((it==inds[val].begin())||(it==(--inds[val].end()))) continue;
            int curr=(*it);
            it--;
            int l=(*it);
            it++;
            if ((curr>=0)&&(curr<n+2)) tmp2[curr]=l;
            it++;
            int r=(*it);
            it--;
            if (l+1==0) segs0.update(0,-1,n+1,r-1,+1);
            else tmp[l+1]=r-1;
        }
    }
    segs.segs=true;
    segs.build(0,0,n+1,tmp);
    prev1.segs=false;
    prev1.build(0,0,n+1,tmp2);
}

//int count1=0;
//int zeroes=0;
vector <int> queries (vector <pair <int, int>> q) {
    vector <int> anss;
    anss.reserve(q.size());
    for (auto [l, r] : q) {
        //count1++;
        l++; r++;
        int different=prev1.query(0,0,n+1,l,r,-1,l-1);
        anss.push_back(segs.query(0,0,n+1,0,l,r,n+1)-2*(n-different));
        //if (anss.back()==0) zeroes++;
    }
    //if (count1==n) cerr << zeroes << endl ;
    return anss;
}

pair <int, int> change (int i, int type, pair <int, int> old) {
    int val=a[i];
    auto it=inds[val].find(i);
    it--;
    int prv=(*it);
    it--;
    int prv2=(*it);
    it++;
    it++;

    it++;
    int nxt=(*it);
    it++;
    int nxt2=(*it);
    it--;
    it--;

    if (type==-1) {
        /// [prv2+1, i-1], [prv+1, nxt-1], [i+1, nxt2-1] -> [prv2+1, nxt-1], [prv+1, nxt2-1]
        segs.update(0,0,n+1,prv2+1,i-1,nxt-1);
        segs.update(0,0,n+1,prv+1,nxt-1,nxt2-1);
        // segs.update2(0,0,n+1,i+1,nxt2-1,-1);

        //prev1.update2(0,0,n+1,i,prv,-1);
        if (nxt!=n+2) prev1.update(0,0,n+1,nxt,i,prv);
    }
    else {
        /// [prv2+1, nxt-1], [prv+1, nxt2-1] -> [prv2+1, i-1], [prv+1, nxt-1], [i+1, nxt2-1]
        segs.update(0,0,n+1,prv2+1,nxt-1,i-1);
        segs.update(0,0,n+1,prv+1,nxt2-1,nxt-1);
        // segs.update2(0,0,n+1,i+1,nxt2-1,+1);
        segs.update(0,0,n+1,i+1,old.first,nxt2-1);

        //prev1.update2(0,0,n+1,i,prv,+1);
        prev1.update(0,0,n+1,i,old.second,prv);
        if (nxt!=n+2) prev1.update(0,0,n+1,nxt,prv,i);
    }
    return {nxt2-1, prv};
}
void update (int i, int v) {
    //count1++;
    i++;
    if (a[i]==v) return ;
    auto old=change(i,-1,{-1, -1});
    inds[a[i]].erase(inds[a[i]].find(i));
    a[i]=v;
    inds[a[i]].insert(i);
    change(i,+1,old);
}
