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

mt19937 rnd(42);
struct treap {
    struct node {
        int x,y;
        int lind,rind;
        int cnt,sum;
        node (int x, int y, int lind, int rind, int cnt, int sum) : x(x), y(y), lind(lind), rind(rind), cnt(cnt), sum(sum) {
        }
    };
    vector <node> nodes;
    int add_node (int x) {
        int ind=nodes.size();
        nodes.push_back(node(x,rnd(),-1,-1,1,1));
        return ind;
    }
    void recover (int curr) {
        int l=nodes[curr].lind,r=nodes[curr].rind;
        nodes[curr].sum=nodes[curr].cnt;
        if (l!=-1) nodes[curr].sum+=nodes[l].sum;
        if (r!=-1) nodes[curr].sum+=nodes[r].sum;
    }
    pair <int, int> split (int curr, int num) {
        if (curr==-1) return {-1, -1};
        if (nodes[curr].x<num) {
            auto [l, r]=split(nodes[curr].rind,num);
            nodes[curr].rind=l;
            recover(curr);
            return {curr, r};
        }
        else {
            auto [l, r]=split(nodes[curr].lind,num);
            nodes[curr].lind=r;
            recover(curr);
            return {l, curr};
        }
    }
    int merge (int l, int r) {
        if (l==-1) return r;
        if (r==-1) return l;
        if (nodes[l].y>nodes[r].y) {
            nodes[l].rind=merge(nodes[l].rind,r);
            recover(l);
            return l;
        }
        else {
            nodes[r].lind=merge(l,nodes[r].lind);
            recover(r);
            return r;
        }
    }

    int root=-1;
    void insert (int x) {
        auto [l, r]=split(root,x);
        auto [rl, rr]=split(r,x+1);
        if (rl==-1) rl=add_node(x);
        else {
            nodes[rl].cnt++;
            nodes[rl].sum++;
        }
        r=merge(rl,rr);
        root=merge(l,r);
    }
    void erase_one (int x) {
        auto [l, r]=split(root,x);
        auto [rl, rr]=split(r,x+1);
        if (rl!=-1) {
            nodes[rl].cnt--;
            nodes[rl].sum--;
            if (nodes[rl].cnt<=0) rl=-1;
        }
        r=merge(rl,rr);
        root=merge(l,r);
    }
    int query_less (int x) {
        auto [l, r]=split(root,x);
        int res=0;
        if (l!=-1) res=nodes[l].sum;
        root=merge(l,r);
        return res;
    }
    int query_greater_equal (int x) {
        auto [l, r]=split(root,x);
        int res=0;
        if (r!=-1) res=nodes[r].sum;
        root=merge(l,r);
        return res;
    }
};

treap segs0;
int n;
int tmp[MAXN+2];
struct tree2d {
    treap 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].insert(init[l]);
            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);
        for (int i=l; i<=r; i++) {
            init[i]=tmp[i];
            if (init[i]!=-1e9) nodes[ind].insert(init[i]);
        }
    }
    int query_less (int ind, int l, int r, int ql, int qr, int val) {
        if ((ql<=l)&&(r<=qr)) return nodes[ind].query_less(val);
        int mid=(l+r)/2;
        int ans=0;
        if (ql<=mid) ans+=query_less(2*ind+1,l,mid,ql,qr,val);
        if (qr>mid) ans+=query_less(2*ind+2,mid+1,r,ql,qr,val);
        return ans;
    }
    int query_greater_equal (int ind, int l, int r, int ql, int qr, int val) {
        if ((ql<=l)&&(r<=qr)) {
            int ans=0;
            if ((segs==true)&&(l==0)) ans+=segs0.query_greater_equal(val);
            ans+=nodes[ind].query_greater_equal(val);
            return ans;
        }
        int mid=(l+r)/2;
        int ans=0;
        if (ql<=mid) ans+=query_greater_equal(2*ind+1,l,mid,ql,qr,val);
        if (qr>mid) ans+=query_greater_equal(2*ind+2,mid+1,r,ql,qr,val);
        return ans;
    }
    void update (int ind, int l, int r, int pos, int old, int new1) {
        if ((segs==true)&&(pos==0)) {
            segs0.erase_one(old);
            segs0.insert(new1);
            return ;
        }
        nodes[ind].erase_one(old);
        nodes[ind].insert(new1);
        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.insert(r-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);
}

vector <int> queries (vector <pair <int, int>> q) {
    vector <int> anss;
    anss.reserve(q.size());
    for (auto [l, r] : q) {
        l++; r++;
        int different=prev1.query_less(0,0,n+1,l,r,l);
        anss.push_back(segs.query_greater_equal(0,0,n+1,0,l,r)-2*(n-different));
    }
    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) {
    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);
}
