#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 MAX_N=1000000;

vector <int> tree(MAX_N,0);
int ver;
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(){};
};

vector <node> cont(MAX_N*40);

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

int update(int x, int index, int ans)
{
	if (x == 0)
		return 0;
	int ind = ++ver, l = cont[x].L, r = cont[x].R;
	if (index < cont[x].val)
		l = update(l, index, ans);
	if (index > cont[x].val)
		l = update(r, index, ans);
	cont[ind] = node(cont[x].val,l,r,cont[x].size + ans);
	return ind;
}

int query(int x, int val)
{
	if (val < cont[x].val)
		return query(cont[x].L,val) + cont[x].size - cont[cont[x].L].size;
	if (val > cont[x].val)
		return query(cont[x].R, val);
	return cont[x].size - cont[cont[x].L].size;
}

map <int,int> exist;

int main()
{
    ios_base::sync_with_stdio(0); //cin.tie(0);
    int n,q;
    cin >>n;
    tree[0]=build(1,n);
    for (int i=0;i<n;i++)
    {
		int x;
		cin >>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;
	}
	cin >>q;
	while (q--)
	{
		int l,r;
		cin >>l>>r;
		cout <<query(tree[r],l)<<"\n";
	}
    return 0;
}