record

#include<bits/stdc++.h>
using namespace std;
int n,m,len,a[1000005],l,r,ans[1000005],cnt[1000005],now_ans;
int from[1000005],ls;
struct node{
    int id,l,r,k;
}p[1000005];
inline bool cmp(node a,node b){
	return a.k^b.k?a.k<b.k:(a.k&1)?a.r<b.r:a.r>b.r;
}
inline void insert(int t){
    if(!cnt[t]) now_ans++;
    cnt[t]++;
}inline void pop(int t){
    cnt[t]--;
    if(!cnt[t]) now_ans--;
}
const int MAXSIZE = 1 << 18;
char buf[MAXSIZE], *p1, *p2;
#define gc()                                                               \
  (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) \
       ? EOF                                                               \
       : *p1++)

int read() {
  int x = 0;
  char c = gc();
  while (!isdigit(c)) {
    c = gc();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
  return x ;
}
void write(int x) {
  int sta[10],top = 0;
  do {
    sta[top++] = x % 10, x /= 10;
  } while (x);
  while (top) putchar(sta[--top] + 48);  // 48 是 '0'
  putchar('\n');
}
int main(){
    //ios::sync_with_stdio(0);
    //cin.tie(0);cout.tie(0);
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(!from[a[i]]) from[a[i]]=++ls;
        a[i]=from[a[i]];
    }
    m=read();
    len=1500;
    for(int i=1;i<=m;i++){
        p[i].id=i;
        p[i].l=read();
        p[i].r=read();
        p[i].k=p[i].l/len;
    }
    sort(p+1,p+1+m,cmp);
    l=0,r=1;
    for(int i=1;i<=m;i++){
        while(l<p[i].r){
            insert(a[++l]);
        }while(l>p[i].r){
            pop(a[l--]);
        }while(r<p[i].l){
            pop(a[r++]);
        }while(r>p[i].l){
            insert(a[--r]);
        }ans[p[i].id]=now_ans;
    }
    for(int i=1;i<=m;i++) write(ans[i]);
    return 0;
}