RT
#include<bits/stdc++.h>
using namespace std;
#define belong(x) ((int)ceil((float)x/len))
inline int read(){
int w = 0, f = 1; char ch = getchar();
while(ch < '0' or ch > '9') {if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' and ch <= '9') w = w*10 + ch - '0', ch = getchar();
return w*f;
}
const int maxn = 1e6 + 5;
int N, M, a[maxn], len;
struct node{
int l, r, id;
inline bool operator <(const node& x) const{
return (belong(l)^belong(x.l))?belong(l)<belong(x.l):((belong(l)&1)?r<x.r:r>x.r);
}
}q[maxn];
int ans[maxn], sum, cnt[maxn];
inline void add(int x){
if(!cnt[x]) sum ++;
cnt[x] ++;
}
inline void del(int x){
if(!(cnt[x]^1)) sum --;
cnt[x] --;
}
int main(){
N = read();
for(int i=1; i<=N; i++) a[i] = read();
len = 1620; M = read();
for(int i=1; i<=M; i++){
int l = read(), r = read();
q[i] = (node){l, r, i};
}
sort(q+1, q+M+1);
int l = 1, r = 0;
for(int i=1; i<=M; i++){
int ql = q[i].l, qr = q[i].r;
while(l < ql) sum -= !--cnt[a[l++]];
while(l > ql) sum += !cnt[a[--l]]++;
while(r < qr) sum += !cnt[a[++r]]++;
while(r > qr) sum -= !--cnt[a[r--]];
ans[q[i].id] = sum;
}
for(int i=1; i<=M; i++) printf("%d\n", ans[i]);
return 0;
}