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

struct multiplicity {
    set <int> once;
    set <int> multiple;
    void add_sorted (int num) {
        if ((once.size()>0)&&(*once.rbegin()==num)) {
            once.erase(--once.end());
            multiple.insert(multiple.end(),num);
        }
        else if ((multiple.size()==0)||(*multiple.rbegin()!=num)) once.insert(once.end(),num);
    }
    void add (int num) {
        if (once.count(num)!=0) {
            once.erase(num);
            multiple.insert(num);
        }
        else if (multiple.count(num)==0) once.insert(num);
    }
    void add (multiplicity& other) {
        for (auto num : other.once) {
            add(num);
        }
        for (auto num : other.multiple) {
            if (once.count(num)!=0) {
                once.erase(num);
                multiple.insert(num);
            }
            else multiple.insert(num);
        }
    }
};
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.size();
            curr.add(nodes[ind]);
            int ans=curr.once.size();
            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) {
    }
};
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;
}
