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

struct multiplicity {
    int once;
    map <int, int> nums;
    void add_sorted (int num) {
        if ((nums.size()>0)&&(nums.rbegin()->first==num)) {
            if (nums.rbegin()->second==1) once--;
            nums.rbegin()->second++;
        }
        else {
            nums.insert(nums.end(),{num, 1});
            once++;
        }
    }
    void add (int num) {
        auto it=nums.find(num);
        if (it!=nums.end()) {
            if (it->second==1) once--;
            it->second++;
        }
        else {
            nums[num]=1;
            once++;
        }
    }
    void add (multiplicity& other) {
        for (auto [num, c] : other.nums) {
            if (c==1) add(num);
            else {
                auto it=nums.find(num);
                if (it!=nums.end()) {
                    if (it->second==1) once--;
                    it->second+=c;
                }
                else {
                    nums[num]=c;
                    if (c==1) once++;
                }
            }
        }
    }
    void remove (int num) {
        auto it=nums.find(num);
        if (it->second==1) {
            once--;
            nums.erase(it);
        }
        else {
            if (it->second==2) once++;
            it->second--;
        }
    }
};
int tmp[MAXN];
struct tree2d {
    multiplicity nodes[4*(MAXN+2)];
    void build (int ind, int l, int r, vector <int>& init) {
        if (l==r) {
            nodes[ind].add_sorted(init[l]);
            return ;
        }
        int mid=(l+r)/2;
        build(2*ind+1,l,mid,init);
        build(2*ind+2,mid+1,r,init);
        merge(init.begin()+l,init.begin()+mid+1,init.begin()+mid+1,init.begin()+r+1,tmp+l);
        for (int i=l; i<=r; i++) {
            init[i]=tmp[i];
            nodes[ind].add_sorted(init[i]);
        }
    }
    multiplicity curr;
    int query (int ind, int l, int r, int ql, int qr) {
        if ((ql<=l)&&(r<=qr)) {
            if ((ql==l)&&(qr==r)) return nodes[ind].once;
            curr.add(nodes[ind]);
            int ans=curr.once;
            if (qr==r) curr=multiplicity();
            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);
        nodes[ind].add(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 tree;

vector <int> a;
int n;
void init (vector <int> a) {
    ::a=a;
    n=a.size();
    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 update (int i, int v) {
    if (a[i]==v) return ;
    tree.update(0,0,n-1,i,a[i],v);
    a[i]=v;
}
