#include "unique.h"
#include<iostream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<algorithm>
#include<vector>
#include<set>
#define MAXN 100000
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_multiset = tree <T, null_type, less_equal <T>, rb_tree_tag, tree_order_statistics_node_update>;
/// less_equal breaks __gnu_pbds tree - find does not work, lower_bound becomes upper_bound and vice versa

ordered_multiset <int> segs0;
int n;
struct tree2d {
    ordered_multiset <int> 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);
        nodes[ind]=nodes[2*ind+1];
        for (auto v : nodes[2*ind+2]) {
            nodes[ind].insert(v);
        }
    }
    int query_less (int ind, int l, int r, int ql, int qr, int val) {
        if ((ql<=l)&&(r<=qr)) return nodes[ind].order_of_key(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.size()-segs0.order_of_key(val));
            ans+=(nodes[ind].size()-nodes[ind].order_of_key(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)) {
            //assert((segs0.upper_bound(old)!=segs0.end())&&(*segs0.upper_bound(old)==old));
            segs0.erase(segs0.upper_bound(old));
            segs0.insert(new1);
            return ;
        }
        //assert((nodes[ind].upper_bound(old)!=nodes[ind].end())&&(*nodes[ind].upper_bound(old)==old));
        nodes[ind].erase(nodes[ind].upper_bound(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);
}
