#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

struct tree2d {
    ordered_multiset <int> nodes[4*MAXN];
    void build (int ind, int l, int r, vector <int>& init) {
        if (l==r) {
            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_greater_equal (int ind, int l, int r, int ql, int qr, int val) {
        if ((ql<=l)&&(r<=qr)) return nodes[ind].size()-nodes[ind].order_of_key(val);
        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 val, int type) {
        //if (type==-1) assert((nodes[ind].upper_bound(val)!=nodes[ind].end())&&(*nodes[ind].upper_bound(val)==val));
        if (type==-1) nodes[ind].erase(nodes[ind].upper_bound(val));
        else nodes[ind].insert(val);
        if (l==r) return ;
        int mid=(l+r)/2;
        if (pos<=mid) update(2*ind+1,l,mid,pos,val,type);
        else update(2*ind+2,mid+1,r,pos,val,type);
    }
    void update2 (int ind, int l, int r, int pos, int old, int new1) {
        //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) update2(2*ind+1,l,mid,pos,old,new1);
        else update2(2*ind+2,mid+1,r,pos,old,new1);
    }
};
tree2d prev1;

set <int> inds[MAXN+1];
vector <int> a;
int n;
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);
    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;
            it--;
            int l=(*it);
            it++;
            tmp[(*it)]=l;
        }
    }
    prev1.build(0,0,n-1,tmp);
}

vector <int> queries (vector <pair <int, int>> q) {
    vector <int> anss;
    anss.reserve(q.size());
    for (auto [l, r] : q) {
        anss.push_back((r-l+1)-2*prev1.query_greater_equal(0,0,n-1,l,r,l));
    }
    return anss;
}

void change (int i, int type) {
    int val=a[i];
    auto it=inds[val].find(i);
    it--;
    int prv=(*it);
    it++;
    it++;
    int nxt=(*it);
    it--;
    if (type==-1) {
        prev1.update(0,0,n-1,i,prv,-1);
        if (nxt!=n) prev1.update2(0,0,n-1,nxt,i,prv);
    }
    else {
        prev1.update(0,0,n-1,i,prv,+1);
        if (nxt!=n) prev1.update2(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);
}
