#include "unique.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#define MAXN 100000
#define LOGN 17
using namespace std;
struct node {
    int sum;
    int lind,rind;
    int time;
};
int roots[MAXN],nums[MAXN];
node tree[2*MAXN+(2*MAXN)*LOGN];
int num;
void build_tree (int ind, int l, int r, vector <int>& vals) {
    if (l==r) {
        tree[ind].sum=vals[l];
        return ;
    }
    int mid=(l+r)/2;
    int lind=tree[ind].lind=num++;
    int rind=tree[ind].rind=num++;
    build_tree(lind,l,mid,vals);
    build_tree(rind,mid+1,r,vals);
    tree[ind].sum=tree[lind].sum+tree[rind].sum;
}
int query (int ind, int l, int r, int qr) {
    if (r<=qr) return tree[ind].sum;
    int mid=(l+r)/2;
    int sum=query(tree[ind].lind,l,mid,qr);
    if (qr>=mid+1) sum+=query(tree[ind].rind,mid+1,r,qr);
    return sum;
}
int update (int ind, int l, int r, int pos, int add, int time) {
    int curr=ind;
    if (tree[curr].time<time) {
        curr=num++;
        tree[curr]=tree[ind];
        tree[curr].time=time;
    }
    tree[curr].sum+=add;
    if (l==r) return curr;
    int mid=(l+r)/2;
    if (pos<=mid) tree[curr].lind=update(tree[ind].lind,l,mid,pos,add,time);
    else tree[curr].rind=update(tree[ind].rind,mid+1,r,pos,add,time);
    return curr;
}

vector <int> a;
int n;
set <int> inds[MAXN+1];
map <int, int> vals;
int nxt[MAXN];
int remove_left (int l, int time) {
    if (nxt[l]==n) return roots[l];
    int next=nxt[l];
    int root=update(roots[l],0,n-1,next,-1,time);
    if (nxt[next]!=n) update(root,0,n-1,nxt[next],+1,time);
    return root;
}
void init_persistent_tree () {
    vector <int> init(n,0);
    for (auto [val, cnt] : vals) {
        auto it=inds[val].begin();
        if (it!=(--inds[val].end())) {
            it++;
            init[*it]=+1;
        }
    }
    num=1;
    build_tree(0,0,n-1,init);
    roots[0]=0; nums[0]=num;
    for (int l=1; l<n; l++) {
        roots[l]=remove_left(l-1,l);
        nums[l]=num;
    }
}
void init (vector <int> a) {
    ::a=a;
    n=a.size();
    for (int i=0; i<n; i++) {
        inds[a[i]].insert(i);
        vals[a[i]]++;
    }
    for (int i=0; i<n; i++) {
        int val=a[i];
        auto it=inds[val].find(i);
        if (it!=(--inds[val].end())) {
            it++;
            nxt[i]=*it;
        }
        else nxt[i]=n;
    }
    init_persistent_tree();
}

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*query(roots[l],0,n-1,r));
    }
    return anss;
}

int change (int i, int type) {
    int val=a[i];
    auto it=inds[val].find(i);
    int prev=-1;
    if (it!=inds[val].begin()) {
        it--;
        prev=(*it);
        it++;
    }
    int next=n;
    if (it!=(--inds[val].end())) {
        it++;
        next=(*it);
        it--;
    }
    if (type==-1) {
        if (prev!=-1) nxt[prev]=next;
    }
    else {
        nxt[i]=next;
        if (prev!=-1) nxt[prev]=i;
    }

    if (prev!=-1) {
        it--;
        if (it==inds[val].begin()) return -1;
        it--;
        return *it;
    }
    return prev;
}
void update (int i, int v) {
    int ind=change(i,-1);
    inds[a[i]].erase(i);
    auto it=vals.find(a[i]);
    it->second--;
    if (it->second==0) vals.erase(it);
    a[i]=v;
    inds[a[i]].insert(i);
    vals[a[i]]++;
    ind=min(ind,change(i,+1));
    if (ind<0) init_persistent_tree();
    else {
        num=nums[ind];
        for (int l=ind+1; l<n; l++) {
            roots[l]=remove_left(l-1,l);
            if ((l==ind+1)&&(roots[l]==roots[l-1])) break;
            nums[l]=num;
        }
    }
}
