#include <bits/stdc++.h>
#define int __int128_t
#define range(VAR, START, END, STEP) for (int(VAR) = (START); (STEP) * (VAR) <= (STEP) * (END); (VAR) += (STEP))
#define loop(END) for (int i = 1; i <= (END); i++)
#define MAXN (signed)(5e3 + 10)
#define pr() putchar('\n')
#define ps() putchar(' ')
#define init(arr, val) memset(arr, val, sizeof(arr))
#define abs_v(x) ((x) >= 0 ? (x) : (-(x)))
using namespace std;
int rt()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    return 1e9 + 10;
}
const int inf = rt();
int read()
{
    int nm = 0, zf = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-')
            zf = -1;
    for (; isdigit(c); c = getchar())
        nm = nm * 10 + (c - '0');
    return nm * zf;
}
void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x >= 10)
        write(x / 10);
    putchar(x % 10 + '0');
}
struct Q
{
    int l, r, t;
} q[MAXN];
int a[MAXN], hsh[signed(5e6+10)],prin[MAXN];
int ans = 0;
int n, m, k, B;
bool cmp(Q x, Q y)
{
    if (x.l / B == y.l / B)
        return x.r < y.r;
    return x.l < y.l;
}
void change(int x, int y)
{
    hsh[x] += y;
    if (hsh[x] == 0)
        ans--;
    if (hsh[x] == 1 && y == 1)
        ans++;
}
signed main()
{
    n = read();
    B = sqrt((long long)n);
    range(i, 1, n, 1)
        a[i] = read();
    m = read();
    range(i, 1, m, 1)
    {
        q[i].l = read(), q[i].r = read(), q[i].t = i;
    }
    sort(q + 1, q + 1 + m, cmp);
    int l = 1, r = 0;
    range(i, 1, m, 1)
    {
        while (l > q[i].l)
            change(a[--l], 1);
        while (l < q[i].l)
            change(a[l++], -1);
        while (r < q[i].r)
            change(a[++r], 1);
        while (r > q[i].r)
            change(a[r--], -1);
        prin[q[m].t]=ans;
    }
    range(i,1,m,1)
    {
        write(prin[i]);
        pr();
    }
    return EXIT_SUCCESS;
}