#include<iostream>
#include<cmath>
#include<bitset>
using namespace std;
const int maxn = 1e6 + 1, maxs = 1e3 + 1;
int n, m, size, num, a[maxn], l[maxn], r[maxn], belong[maxn], s[maxs][maxs], st[maxs], ed[maxs], last[maxn];
bitset<maxn> vis;
inline int read()
{
	register int s = 0;
	char ch = getchar();
	while(ch > '9' || ch < '0')
	{
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
	{
		s = (s << 3) + (s << 1) + (ch ^ 48);
		ch = getchar();
	}
	return s;
}
inline void write(int x)
{
	if(x > 9)
	{
		write(x / 10);
	}
	putchar((x % 10) ^ 48);
}
int main(){ 
	n = read();
	fill(r, r + 1 + maxn, maxn + 1);
	size = pow(n, 0.5);
	num = ceil(n / size);
	for(register int i = 1; i <= n; ++i)
	{
		a[i] = read();
		l[i] = last[a[i]];
		r[l[i]] = i;
		last[a[i]] = i;
	}
	for(register int i = 1; i <= num; ++i)
	{
		st[i] = ed[i - 1] + 1;
		ed[i] = min(n, i * size);
		vis.reset();
		for(register int j = st[i]; j <= ed[i]; ++j)
		{
			belong[j] = i;
			s[i][i] += !vis[a[j]];
			vis[a[j]] = 1;
		}
	}
	for(register int i = 1; i < num; ++i)
	{
		for(register 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];
			}
		}
	}
	m = read();
	while(m--)
	{
		register int x = read(), y = read();
		register int sum = s[belong[x] + 1][belong[y] - 1];
		if(belong[y] - belong[x] <= 1)
		{
			vis.reset();
			for(int i = x; i <= y; ++i)
			{
				sum += !vis[a[i]];
				vis[a[i]] = 1;
			}
			write(sum);
			putchar('\n');
			continue;
		}
		for(register int i = x; i <= ed[belong[x]]; ++i)
		{
			sum += r[i] > y;
		}
		for(register int i = st[belong[y]]; i <= y; ++i)
		{
			sum += l[i] < st[belong[x] + 1];
		}
		write(sum);
		putchar('\n');
	}
	return 0;
}