#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;

int n, m;
int a[N], ans[N];
int tr[N], last[N];
struct Node{
	int l, r;
	int id;
	bool operator < (const Node& t) const{
		if(l != t.l)	return l < t.l;
		return r < t.r;
	};
}p[N];

int lowbit(int x)
{
	return x & -x;
}

void add(int x, int v)
{
	for(int i = x;i < N;i += lowbit(i))
		tr[i] += v;
}

int query(int x)
{
	int res = 0;
	for(int i = x;i;i -= lowbit(i))
		res += tr[i];
	return res;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1;i <= n;i ++ )	scanf("%d", &a[i]);
	scanf("%d", &m);
	for(int i = 1;i <= m;i ++ )	
	{
		int l, r;
		scanf("%d%d", &l, &r);
		p[i] = {l, r, i};
	}
	sort(p + 1, p + 1 + m);
	int j = 1;
	for(int i = 1;i <= m;i ++ )
	{
		for(j;j <= p[i].r;j ++ )
		{
			int v = a[j];
			if(last[v])	add(last[v], -1);
			
			add(j, 1);
			last[v] = j;
		}
		ans[p[i].id] = query(p[i].r) - query(p[i].l - 1);
	}
	for(int i = 1;i <= m;i ++ )	cout << ans[i] << endl;
	return 0;
}