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

struct multiplicity {
    unordered_map <int, int> once;
    set <pair <int, int>> nums_inds;
    void add (int num, int ind) {
        auto it=nums_inds.lower_bound({num, -1});
        if ((it!=nums_inds.end())&&(it->first==num)) {
            it++;
            if ((it==nums_inds.end())||(it->first!=num)) once.erase(num);
            it--;
            nums_inds.insert({num, ind});
        }
        else {
            nums_inds.insert({num, ind});
            once[num]=ind;
        }
    }
    void add (multiplicity& other) {
        for (auto [num, ind] : other.nums_inds) {
            add(num,ind);
        }
    }
    void remove (int num, int ind) {
        nums_inds.erase({num, ind});
        auto it=nums_inds.lower_bound({num, -1});
        if ((it==nums_inds.end())||(it->first!=num)) once.erase(num);
        else {
            it++;
            if ((it==nums_inds.end())||(it->first!=num)) {
                it--;
                once[it->first]=it->second;
            }
        }
    }
};
//pair <int, int> tmp[MAXN],tmp2[MAXN];
int prv[MAXN],nxt[MAXN];
struct tree2d {
    multiplicity nodes[4*(MAXN+2)];
    void build (int ind, int l, int r, vector <int>& init) {
        if (l==r) {
            //tmp[l]={init[l], l};
            nodes[ind].add(init[l],l);
            return ;
        }
        int mid=(l+r)/2;
        build(2*ind+1,l,mid,init);
        build(2*ind+2,mid+1,r,init);
        //merge(tmp+l,tmp+mid+1,tmp+mid+1,tmp+r+1,tmp2+l);
        for (int i=l; i<=r; i++) {
            //tmp[i]=tmp2[i];
            nodes[ind].add(init[i],i);
        }
    }
    int query (int ind, int l, int r, int ql, int qr) {
        if ((ql<=l)&&(r<=qr)) {
            int ans=nodes[ind].once.size();
            if ((ql==l)&&(qr==r)) return ans;
            for (auto [num, ind] : nodes[ind].once) {
                if ((nxt[ind]<=qr)||(prv[ind]>=ql)) ans--;
            }
            return ans;
        }
        int mid=(l+r)/2;
        int ans=0;
        if (ql<=mid) ans+=query(2*ind+1,l,mid,ql,qr);
        if (qr>mid) ans+=query(2*ind+2,mid+1,r,ql,qr);
        return ans;
    }
    void update (int ind, int l, int r, int pos, int old, int new1) {
        nodes[ind].remove(old,pos);
        nodes[ind].add(new1,pos);
        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 tree;

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);
    }
    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--;
            prv[curr]=(*it);
            it++;
            it++;
            nxt[curr]=(*it);
            it--;
        }
    }
    tree.build(0,0,n-1,a);
}

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

void change (int i, int type) {
    int val=a[i];
    auto it=inds[val].find(i);
    it--;
    int prev=(*it);
    it++;
    it++;
    int next=(*it);
    it--;
    if (type==-1) {
        if (prev!=-1) nxt[prev]=next;
        if (next!=n) prv[next]=prev;
    }
    else {
        prv[i]=prev; nxt[i]=next;
        if (prev!=-1) nxt[prev]=i;
        if (next!=n) prv[next]=i;
    }
}
void update (int i, int v) {
    if (a[i]==v) return ;
    tree.update(0,0,n-1,i,a[i],v);
    change(i,-1);
    inds[a[i]].erase(i);
    a[i]=v;
    inds[a[i]].insert(i);
    change(i,+1);
}
