#include "unique.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#define MAXN 100000
using namespace std;
vector <int> a;
int n;
set <int> inds[MAXN+1];
map <int, int> vals;
int nxt[MAXN];
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;
    }
}

int bit[MAXN+1];
void update_bit (int ind, int val) {
    int pos=ind+1;
    for (;;) {
        if (pos>n) break;
        bit[pos]+=val;
        pos+=(pos&(-pos));
    }
}
int query_bit (int ind) {
    int pos=ind+1;
    int res=0;
    for (;;) {
        if (pos==0) break;
        res+=bit[pos];
        pos-=(pos&(-pos));
    }
    return res;
}
void remove_left (int l) {
    update_bit(l,-1);
    if (nxt[l]==n) return ;
    int next=nxt[l];
    update_bit(next,+2); // -1 -> +1
    if (nxt[next]!=n) update_bit(nxt[next],-1);
}
vector <int> queries (vector <pair <int, int>> q) {
    vector <tuple <int, int, int>> queries;
    for (int i=0; i<q.size(); i++) {
        queries.push_back({q[i].first, q[i].second, i});
    }
    sort(queries.begin(),queries.end());
    for (auto [val, cnt] : vals) {
        auto it=inds[val].begin();
        update_bit(*it,+1);
        if (it!=(--inds[val].end())) {
            it++;
            update_bit(*it,-1);
        }
    }
    vector <int> anss(q.size());
    int prv=0;
    for (auto [l, r, curr] : queries) {
        for (int ind=prv; ind<l; ind++) {
            remove_left(ind);
        }
        anss[curr]=query_bit(r);
        prv=l;
    }
    for (int ind=prv; ind<n; ind++) {
        remove_left(ind);
    }
    return anss;
}

void 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;
    }
}
void update (int i, int v) {
    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]]++;
    change(i,+1);
}
