P

#include <bits/stdc++.h>
#define mp make_pair

using namespace std;

int n,Q;
int tab[50005], przenum[50005];
int odpowiedz[100005];
map <int,int> prz;
int rozne [50005];
int ile=0;

int WskL = -1;
int WskP = -1;

priority_queue <pair <int,pair<int,pair <int,int> > > > kolej;  // grupa, kon, pocz, zapytanie

void Pprzes(int a)
{
	if (a < WskP)
	{
		while (WskP > a)
		{
			rozne[tab[WskP]]--;
			if (rozne[tab[WskP]] == 0) ile--;
			WskP--;
		}
	}
	else
	{
		while (WskP < a)
		{
			WskP++;
			rozne[tab[WskP]]++;
			if (rozne[tab[WskP]] == 1) ile++;
		}
	}
}
void Lprzes(int a)
{
	if (a < WskL)
	{
		while (WskL > a)
		{
			WskL--;
			rozne[tab[WskL]]++;
			if (rozne[tab[WskL]] == 1) ile++;
		}
	}
	else
	{
		while (WskL < a)
		{
			rozne[tab[WskL]]--;
			if (rozne[tab[WskL]] == 0) ile--;
			WskL++;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for (int i=0;i<n;i++)
	{
		cin>>tab[i];
		przenum[i] = tab[i];
	}

	sort(przenum, przenum+n);
	int licz = 1;
	for (int i=0;i<n;i++)
	{
		prz[przenum[i]] = licz;
		if (przenum[i] != przenum[i+1]) licz ++;
	}
	for (int i=0;i<n;i++)
	{
		tab[i] = prz[tab[i]];
	}

	int pierw = sqrt(n);
	cin>>Q;
	for (int q=0;q<Q;q++)
	{
		int a,b;
		cin>>a>>b;
		kolej.push(mp(a/pierw,mp(b,mp(a,q))));
	}
	while (!kolej.empty())
	{
		bool czy = 0;
		int pocz = kolej.top().second.second.first - 1;
		int kon = kolej.top().second.first - 1;
		int zapytanie = kolej.top().second.second.second;
		if (pocz == -1 && tab[0]!=0) czy = 1, pocz = 0;
		kolej.pop();

		Pprzes(kon);
		Lprzes(pocz);
		odpowiedz[zapytanie] = ile + czy;
	}

	for (int i=0;i<Q;i++)
	{
		cout<<odpowiedz[i]<<"\n";
	}

	return 0;
}