record

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read()
{
    ll x = 0, t = 1; char ch;
    while (!isdigit(ch = getchar_unlocked())) if (ch == '-') t = -1;
    do x = x * 10 + ch - '0'; while (isdigit(ch = getchar_unlocked()));
    return x * t;
}
void write(ll x)
{
    if (x < 0) { putchar('-'); x = -x; }
    ll a[10] = {0};
    while (x) { a[++a[0]] = x % 10; x /= 10; }
    while (a[0]) putchar(a[a[0]--] + '0');
}
const ll maxn = 1e6 + 10;
struct node
{
    ll id, l, r;
} q[maxn];
ll n, a[maxn], m, ans[maxn], cnt[maxn], cur, siz, d[maxn], dcnt;
bool operator<(node l, node r)
{
    if (l.l / siz != r.l / siz)
    {
        return l.l < r.l;
    }
    if (l.l / siz % 2)
    {
        return l.r < r.r;
    }
    else
    {
        return l.r > r.r;
    }
}
void solve()
{
    n = read();
    siz = sqrt(n);
    for (ll i = 1; i <= n; i++)
    {
        a[i] = read();
        if (!d[a[i]])
        {
            d[a[i]] = ++dcnt;
        }
        a[i] = d[a[i]];
    }
    m = read();
    for (ll i = 1; i <= m; i++)
    {
        q[i].l = read();
        q[i].r = read();
        q[i].id = i;
    }
    sort(q + 1, q + 1 + m);
    ll l = 1, r = 0;
    for (ll i = 1; i <= m; i++)
    {
        while (l > q[i].l)
        {
            if (++cnt[a[--l]] == 1)
            {
                cur++;
            }
        }
        while (r < q[i].r)
        {
            if (++cnt[a[++r]] == 1)
            {
                cur++;
            }
        }
        while (l < q[i].l)
        {
            if (!--cnt[a[l++]])
            {
                cur--;
            }
        }
        while (r > q[i].r)
        {
            if (!--cnt[a[r--]])
            {
                cur--;
            }
        }
        ans[q[i].id] = cur;
    }
    for (ll i = 1; i <= m; i++)
    {
        write(ans[i]);
        putchar('\n');
    }
}
int main()
{
	ll t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}