#include<iostream>
#include<cmath>
using namespace std;
const int maxn = 1e6 + 1, maxs = 1e3 + 1;
int n, m, sum, x, y, size, num, vis[maxn], a[maxn], l[maxn], r[maxn], belong[maxn], s[maxs][maxs], st[maxs], ed[maxs], last[maxn];
int main(){ 
	scanf("%d", &n);
	fill(r, r + 1 + maxn, n + 1);
	size = pow(n, 0.5);
	num = ceil(n / size);
	for(int i = 1; i <= n; ++i)
	{
		scanf("%d", &a[i]);
		l[i] = last[a[i]];
		r[l[i]] = i;
		last[a[i]] = i;
	}
	for(int i = 1; i <= num; ++i)
	{
		st[i] = ed[i - 1] + 1;
		ed[i] = min(n, i * size);
		fill(vis, vis + 1 + maxs, 0);
		for(int j = st[i]; j <= ed[i]; ++j)
		{
			belong[j] = i;
			s[i][i] += !vis[a[j]]++;
		}
	}
	for(int i = 1; i < num; ++i)
	{
		for(int j = 1; i + j <= num; ++j)
		{
			s[i][i + j] = s[i][i + j - 1];
			for(int k = st[i + j]; k <= ed[i + j]; ++k)
			{
				s[i][i + j] += l[k] < st[i];
			}
		}
	}
	scanf("%d", &m);
	while(m--)
	{
		scanf("%d %d", &x, &y);
		int sum = s[belong[x] + 1][belong[y] - 1];
		if(belong[y] - belong[x] <= 1)
		{
			fill(vis, vis + 1 + maxs, 0);
			for(int i = x; i <= y; ++i)
			{
				sum += !vis[a[i]]++;
			}
			printf("%d\n", sum);
			continue;
		}
		for(int i = x; i <= ed[belong[x]]; ++i)
		{
			sum += r[i] > y;
		}
		for(int i = st[belong[y]]; i <= y; ++i)
		{
			sum += l[i] < st[belong[x] + 1];
		}
		printf("%d\n", sum);
	}
	return 0;
}