#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <cstdio>
#include <vector>
#include <stack>

#define int long long
#define pb push_back
#define rep(a,b,c) for(auto a=b;a<=c;++a)
#define per(a,b,c) for(auto a=b;a>=c;--a)

typedef long long ll;

const int N = 2e5 + 10;

namespace Space {
	auto ls = [](auto x) {return x << 1;};
	auto rs = [](auto x) {return x << 1 | 1;};	

	template < typename _Tp >
	inline _Tp read() {
		auto f = 1, a = 0;
		char ch = getchar ();
		while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = getchar ();
		while (ch >= '0' && ch <= '9') a = (a << 1) + (a << 3) + (ch ^ '0'), ch = getchar ();
		return{a * f};
	}
	template < typename _Tp >
	inline void write(_Tp x){
	    if(x < 0) putchar('-'), x = -x;
	    if(x >= 10) write(x / 10);
	    putchar('0' + x % 10);
	}
	
}

namespace StrTree{
	struct strtree {
		int l, r, sum;
	}tree[N << 2];
	struct Node{
		int l, r, id;
		bool operator < (const Node& b)const {
			return r < b.r;
		}
	}q[N];
}

using namespace Space;
using namespace StrTree;

std::vector <int> v[N];
int n, m, a[N], last[N], ans[N];

class Sol{
private:
	inline void pushup(int x) {
		tree[x].sum = tree[ls(x)].sum + tree[rs(x)].sum;
	}
	inline void build(int x, int l, int r) {
		tree[x] = {l, r, 1};
		if (l == r) return;
		auto mid = (l + r) >> 1;
		build (ls(x), l, mid); 
		build (rs(x), mid + 1, r);
		pushup(x);
	}
	inline void change(int u, int x) {
		if (tree[u].l == x && tree[u].r == x) {
			tree[u].sum = 0;
			return;
		}
		auto mid = (tree[u].l + tree[u].r) >> 1;
		if (x <= m) change(ls(u), x);
		else change(rs(u), x);
		pushup(u);
	}
	inline int query (int u, int x, int y) {
		if (x > tree[u].r || y < tree[u].l) return 0;
		if (x <= tree[u].l && tree[u].r <= y) return{tree[u].sum};
		return{query(ls(u), x, y) + query(rs(u), x, y)};
	}	
public:
	inline void sol() {
		n = read<int>();
		rep(i,1,n) a[i] = read<int>();
		m = read<int>();
		rep(i,1,m) {
			q[i].l = read<int>(), q[i].r = read<int>();
			q[i].id = i;
		}
		std::sort(q + 1, q + m + 1);
		rep(i,1,m) v[q[i].r].pb(i);
		build (1, 1, n);
		rep(i,1,n) {
			if (last[a[i]]) change(1, last[a[i]]);
			last[a[i]] = i;
			for (auto t : v[i]) ans[q[t].id] = query(1, q[t].l, q[t].r);
		}
		rep(i,1,m) std::cout << ans[i] << '\n';
	}
}T;

signed main() {
	T.sol();
}