题目地址：https://www.spoj.com/problems/DQUERY/

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128=__int128;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using db = double;
using ldb = long double;
#define F first
#define S second
int sq;
struct MO{
    int l,r,id;
    bool operator<(const MO &o)const{
        if(l/sq!=o.l/sq) return l<o.l;
        if((l/sq)&1) return r<o.r;
        return r>o.r;
    }
};
void solve(){
    int n;cin>>n;
    sq=sqrt(n);
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int q;cin>>q;
    vector<MO> mo(q+1);
    vector<int> res(q+1);
    for(int i=1;i<=q;i++){
        cin>>mo[i].l>>mo[i].r;
        mo[i].id=i;
    }
    sort(mo.begin()+1,mo.end());
    vector<int> cnt(1e6+1);
    int l=1,r=0;
    int ans=0;
    auto add=[&](int x)->void {
        if(!cnt[x]) ans++;
        cnt[x]++;
    };
    auto del=[&](int x)->void {
        if(cnt[x]==1) ans--;
        cnt[x]--;
    };
    // cout<<ans<<"\n";
    for(int i=1;i<=q;i++){
        while(l<mo[i].l) del(a[l++]);
        while(l>mo[i].l) add(a[--l]);
        while(r>mo[i].r) del(a[r--]);
        while(r<mo[i].r) add(a[++r]);
        res[mo[i].id]=ans;
    }
    for(int i=1;i<=q;i++){
        cout<<res[i]<<"\n";
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}