/*
Code by stringdp100005.
*/
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = int64_t;
using ui32 = uint32_t;
using ui64 = uint64_t;
int t;
#define string int
string dp[100005];
#undef string
namespace strdp {
void init() {
}
const int N = 1e6;
struct node {
int l, r, p, idx;
} q[N + 5];
int a[N + 5], ans[N + 5];
int sum, cnt[N + 5], d[N + 5];
inline void add(int i) {
sum += (cnt[i] == 0);
cnt[i]++;
}
inline void del(int i) {
cnt[i]--;
sum -= (cnt[i] == 0);
}
inline void read(int &x) {
x = 0;
char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) {
x = x * 10 + (ch - '0');
ch = getchar();
}
}
inline void write(int x) {
if (x == 0) {
putchar('0');
return;
}
int a[20] = {}, c = 0;
while (x) {
a[++c] = x % 10;
x /= 10;
}
for (int i = c; i >= 1; i--) putchar(a[i] + '0');
}
void main(int cas) {
int n, m;
read(n);
int cnt = 0;
for (int i = 1; i <= n; i++) {
read(a[i]);
if (!d[a[i]]) d[a[i]] = ++cnt;
a[i] = d[a[i]];
}
read(m);
int blk = sqrt(n);
for (int i = 1; i <= m; i++) {
read(q[i].l);
read(q[i].r);
q[i].idx = i;
q[i].p = q[i].l / blk;
}
sort(q + 1, q + m + 1, [&](node x, node y) {
if (x.p != y.p) {
return x.p < y.p;
}
return x.r < y.r;
});
for (int i = 1, l = 1, r = 0; i <= m; i++) {
while (l > q[i].l) add(a[--l]);
while (r < q[i].r) add(a[++r]);
while (l < q[i].l) del(a[l++]);
while (r > q[i].r) del(a[r--]);
ans[q[i].idx] = sum;
}
for (int i = 1; i <= m; i++) {
write(ans[i]);
putchar('\n');
}
}
}
// #define multipleTestCases
i32 main() {
#ifdef multipleTestCases
cin >> t;
#else
t = 1;
#endif
for (int i = 1; i <= t; i++) {
strdp::init();
strdp::main(i);
putchar('\n');
}
return 0;
}
@Erin 此帖结