#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-8
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 1000005;
struct node
{
    int l, r, k;
} q[N];
int pos[N], ans[N], cnt[N], a[N];
bool cmp(node a, node b)
{
    if (pos[a.l] != pos[b.l])
        return pos[a.l] < pos[b.l];
    if (pos[a.l] & 1)
        return a.r > b.r;
    return a.r < b.r;
}
int ANS = 0;
void add(int x)
{
    cnt[a[x]]++;
    if (cnt[a[x]] == 1)
        ANS++;
}
void del(int x)
{
    cnt[a[x]]--;
    if (cnt[a[x]] == 0)
        ANS--;
}
int main()
{
    int n;
    scanf("%d", &n);
    int block = sqrt(n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        pos[i] = (i - 1) / block + 1;
    }
    int m;
    scanf("%d", &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].k = i;
    }
    sort(q + 1, q + 1 + m, cmp);
    int L = 1, R = 0;
    for (int i = 1; i <= m; i++)
    {
        while (L < q[i].l)
            del(L++);
        while (R > q[i].r)
            del(R--);
        while (L > q[i].l)
            add(--L);
        while (R < q[i].r)
            add(++R);
        ans[q[i].k] = ANS;
    }
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i]);
    return 0;
}