#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define ll long long
using namespace std;

const int N = 1e6 + 5;

int n, m;
int a[N], c[N];
int pre[N];

struct Node {
	int l, r;
	int pos;
};

int read() {
	int x = 0, w = 1;
	char c = 0;
	while(c < '0' || c > '9') {
		if(c == '-')
			w = -1;
		
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		x = x*10+(c-'0');
		c = getchar();
	}
	
	return x * w;
}

void add(int x, int y) {
	for(; x<=N; x+=(x & -x))
		c[x] += y;
}

int ask(int x, int y) {
	int res = 0;
	for(; y; y-=(y & -y))
		if(c[y] < x)
			res++;
		
	return res;
}

void get_pre() {
	for(int i=1; i<=n; i++) {
		int t = a[i];
		for(int j=i-1; j>=1; j--)
			if(a[j] == t) {
				pre[i] = j;
				add(i, pre[i]);
				break;
			}
	}
}

int main() {
	n = read();
	for(int i=1; i<=n; i++)
		a[i] = read();
		
	get_pre();
	
	m = read();
	while(m--) {
		int l, r;
		l = read(), r = read();
		int ans = 0;
		ans += ask(1, r) - ask(1, l - 1);
		
		printf("%d\n", ans);
		
	}
	return 0;
}