#include <vector>
#include <cmath>
#include <ctype.h>
#include <cassert>
#include <ctime>
#include <climits>
#include <limits>
#include <algorithm>
#include <list>
#include <set>
#include <map>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <iomanip>
#include <bitset>
#include <utility>
#include <deque>
#include <stdlib.h>
#include <functional>
//#define C11
//#include <windows.h>

#ifdef C11
#include <unordered_map>
    #include <unordered_set>
    #include <tuple>
#endif // C11

#define F first
#define S second
#define mp make_pair
#define pb push_back
#define fabs(x) ((x>0) ? (x) : -1*(x))
#define show(a,n) cout <<#a<<": "; for (int iii=0;iii<n;iii++) cout <<a[iii]<<" "; cout<<"\n";
#define show2(a,n,m) cout <<#a<<":\n"; for (int iii=0;iii<n;iii++) { for(int jjj=0;jjj<m;jjj++) cout <<a[iii][jjj]<<" "; cout <<"\n";}
#define name(x) cout <<#x<<" \n";
#define print(x) cout <<#x"="<<x<<"\n";
#define letters char alp[30]={qwertyuiopasdfghjklzxcvbnm},sogl[30]={qwrtpsdfghjklzxcvbnm},gl[30]={eyuioa};
#define SetBit(value,place) (value|(1<<place))
#define ClearBit(value,place) (value&(~(1<<place)))
#define InverseBit(value,place) (value^(1<<place))
#define StartClock time_t inittime=clock();
#define GetClock fprintf(stderr,"Time: %f\n",1.0*(clock()-inittime)/CLOCKS_PER_SEC);

typedef std::pair<int,int> pii;
typedef std::vector <int>::iterator iti;
typedef std::multiset <int>::iterator itm;
typedef std::set <int>::iterator itset;
typedef std::string::iterator its;
typedef std::pair<long long,long long> pll;
typedef std::vector <std::vector <int> > graph;
typedef unsigned long long ull;
typedef unsigned int ui;

using namespace std;

const int INF=INT_MAX;
const long long LINF=LLONG_MAX;
const unsigned long long ULINF=ULLONG_MAX;
const double EPS=0.000001;
const int mod=1000000007;

#define ONLINE_JUDGE

#ifndef ONLINE_JUDGE
#include <fstream>
    ifstream cin("input.txt");
    ofstream cout("output.txt");
#else
#include <iostream>
#endif // LOCAL

const int MAXN = 1000000;
int tree[MAXN];
int tr_cnt;
struct node {
    int val, l, r, size;

    node (int v ,int L ,int R , int s )
    {
        val = v;
        l = L;
        r = R;
        size = s;
    }
    node(){};
};

node* ver = new node[40 * MAXN];

int build( int l, int r)
{
    if ( l > r)
        return 0;
    int ind = ++tr_cnt;
    int m = ( l + r)>>1;
    ver[ind] = node(m, build(l, m - 1 ), build( m + 1, r), 0 );
    return ind;
}

int update( int x, int value, int amount )
{
    if ( x == 0 )
        return 0;
    int idx = ++tr_cnt;
    int L = ver[x].l;
    int R = ver[x].r;
    if ( value < ver[x].val )
        L = update( L, value, amount );
    if ( value > ver[x].val )
        R = update( R, value, amount );
    ver[idx] = node(ver[x].val, L, R, ver[x].size + amount );
    return idx;
}

int query( int x, int value)
{
    if ( value < ver[x].val )
        return query( ver[x].l, value) + ver[x].size -  ver[ ver[x].l].size;
    if ( value > ver[x].val )
        return query( ver[x].r, value);
    return ver[x].size - ver[ ver[x].l].size;
}

int main()
{
    int n,q;
    scanf( "%d", &n );
    map< int, int > exist;
    tree[0] = build( 1, n );
    for ( int i = 1; i <= n; i++ )
    {
        int x;
        scanf( "%d", &x );
        if ( exist[x] != 0 )
            tree[i] = update( update( tree[i - 1], exist[x], -1 ), i, +1 );
        else
            tree[i] = update( tree[i - 1], i, +1 );
        exist[x] = i;
    }

    scanf( "%d", &q );
    while ( q-- ) {
        int l, r;
        scanf( "%d %d", &l, &r);
        printf( "%d\n", query( tree[r], l) );
    }
    return 0;
}