//author @ Ayush Aggarwal
// Let's Do this shit.
#include <bits/stdc++.h>
using namespace std;
//typedef long int;
int freq[1000006];
int a[300003];
int block_size;
struct query
{
    int L,R,idx;
};
query q[200002];
bool compare(query q1,query q2)
{
    int L1 = q1.L/block_size;
    int L2 = q2.L/block_size;
    if(L1!=L2)
        return L1 < L2;
    return q1.R < q1.R;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    //memset(freq,0,sizeof(freq));
    int N,L1,R1;
    scanf("%d",&N);
    for(int i=0;i<N;i++)
        scanf("%d",&a[i]);
    block_size = (int)sqrt(N);
    int Q;
    cin>>Q;
    //query q[Q];
    for(int i=0;i<Q;i++)
    {
        scanf("%d%d",&L1,&R1);
        L1--;
        R1--;
        q[i].L = L1;
        q[i].R = R1;
        q[i].idx = i;
    }
    sort(q,q+Q,compare);
    int curr_L=0,curr_R=-1;
    int count=0;
    int sum[Q];
    for(int i=0;i<Q;i++)
    {
         L1 = q[i].L;
         R1 = q[i].R;
        int prev=0;
        while(curr_L < L1)
        {
            freq[a[curr_L]]--;
            if(freq[a[curr_L]]==0)
                count--;
            curr_L++;
        }
        while(curr_L > L1)
        {
            curr_L--;
            freq[a[curr_L]]++;
            if(freq[a[curr_L]]==1)
                count++;
        }
        while(curr_R < R1)
        {
            curr_R++;
            freq[a[curr_R]]++;
            if(freq[a[curr_R]]==1)
                count++;
        }
        while(curr_R > R1)
        {
            freq[a[curr_R]]--;
            if(freq[a[curr_R]]==0)
                count--;
            curr_R--;
        }
        //cout<<freq[1]<<" "<<freq[2]<<" "<<freq[3]<<endl;
        sum[q[i].idx] = count;
    }
    for(int i=0;i<Q;i++)
        printf("%d\n",sum[i]);
    return 0;
}