#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e6+5;
int n , m , a[maxn] , bel[maxn] , L , R , pre[maxn] , lst[maxn] , suf[maxn] , B;
int ans[maxn] , res;
inline int read(){int x=0;char ch=getchar();while(isdigit(ch) ^ 1)ch=getchar();while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return x;}
inline void print(int x){if (x > 9)print(x/10);putchar(x%10|48);}
struct qu{int l , r , id;}q[maxn];
bool cmp(qu x , qu y){return bel[x.l] == bel[y.l] ? bel[x.l] & 1 ? x.r < y.r : x.r > y.r : bel[x.l] < bel[y.l];}
inline int Query(int l , int r)
{
	if (L > n || R > n) {cerr << 0;exit(0);}
	while(l < L)res+=suf[--L] > R;
	while(r > R)res+=pre[++R] < L;
	while(l > L)res-=suf[L++] > R;
	while(r < R)res-=pre[R--] < L;
	return res;
}
int main ()
{
//	freopen("in.txt" , "r" , stdin);
//	freopen("out.txt" , "w" , stdout);
	n=read();
	for (int i = 1; i <= n; i++)a[i]=read();
	m=read();
	B = max(sqrt(n * n / m) , 1.0);
	for (int i = 1; i <= n; i++)
	{
		bel[i]=(i - 1)/B+1;
		pre[i]=lst[a[i]];
		lst[a[i]]=i;
	}
	for (int i = 0; i <= n; i++)lst[a[i]]=n + 1;
	for (int i = n; i; i--)
	{
		suf[i]=lst[a[i]];
		lst[a[i]]=i;
	}
	L=R=1;
	res=1;
	for (int i = 1; i <= m; i++)q[i].l=read(),q[i].r=read(),q[i].id=i;
	sort(q + 1 , q + m + 1 , cmp);
	for (int i = 1; i <= m; i++)ans[q[i].id]=Query(q[i].l , q[i].r);
	for (int i = 1; i <= m; i++) printf("%d\n",ans[i]);
	return 0;
}