#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];
struct tree2d {
    dynamic_segment_tree nodes[4*MAXN];
    bool segs;
    void build (int ind, int l, int r, vector <int>& init) {
        for (int i=l; i<=r; i++) {
            if (init[i]!=-1e9) nodes[ind].update(0,-1,n-1,init[i],+1);
        }
        if (l==r) return;
        int mid=(l+r)/2;
        build(2*ind+1,l,mid,init);
        build(2*ind+2,mid+1,r,init);
    }
    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);
    }
    void update2 (int ind, int l, int r, int pos, int val, int type) {
        if ((segs==true)&&(pos==0)) {
            if (type==-1) segs0.update(0,-1,n-1,val,-1);
            else segs0.update(0,-1,n-1,val,+1);
            return ;
        }
        if (type==-1) nodes[ind].update(0,-1,n-1,val,-1);
        else nodes[ind].update(0,-1,n-1,val,+1);
        if (l==r) return ;
        int mid=(l+r)/2;
        if (pos<=mid) update2(2*ind+1,l,mid,pos,val,type);
        else update2(2*ind+2,mid+1,r,pos,val,type);
    }
};
tree2d segs,prev1;

set <int> inds[MAXN+1];
vector <int> a;
void init (vector <int> a) {
    ::a=a;
    n=a.size();
    for (int val=1; val<=n; val++) {
        inds[val].insert(-1);
        inds[val].insert(n);
    }
    for (int i=0; i<n; i++) {
        int val=a[i];
        inds[val].insert(i);
    }
    vector <int> tmp(n,-1e9),tmp2(n);
    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++;
            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 count_different (int l, int r) {
    return prev1.query(0,0,n-1,l,r,-1,l-1);
}
vector <int> queries (vector <pair <int, int>> q) {
    vector <int> anss;
    anss.reserve(q.size());
    for (auto [l, r] : q) {
        int different=count_different(l,r);
        anss.push_back(segs.query(0,0,n-1,0,l,r,n-1)-(count_different(0,r)-different)-(count_different(l,n-1)-different));
    }
    return anss;
}

void change (int i, int type) {
    int val=a[i];
    auto it=inds[val].find(i);
    it--;
    int prv=(*it),prv2=-1e9;
    if (prv!=-1) {
        it--;
        prv2=(*it);
        it++;
    }
    it++;

    it++;
    int nxt=(*it),nxt2=1e9;
    if (nxt!=n) {
        it++;
        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]
        if (prv2!=-1e9) segs.update(0,0,n-1,prv2+1,i-1,nxt-1);
        if (nxt2!=1e9) segs.update(0,0,n-1,prv+1,nxt-1,nxt2-1);
        else segs.update2(0,0,n-1,prv+1,nxt-1,-1);
        if (nxt2!=1e9) segs.update2(0,0,n-1,i+1,nxt2-1,-1);

        prev1.update2(0,0,n-1,i,prv,-1);
        if (nxt!=n) 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]
        if (prv2!=-1e9) segs.update(0,0,n-1,prv2+1,nxt-1,i-1);
        if (nxt2!=1e9) segs.update(0,0,n-1,prv+1,nxt2-1,nxt-1);
        else segs.update2(0,0,n-1,prv+1,nxt-1,+1);
        if (nxt2!=1e9) segs.update2(0,0,n-1,i+1,nxt2-1,+1);

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