https://www.luogu.com.cn/problem/P1972

const int N = 1000010;
#define mid  ((l+r)>>1)
int n, m, a[N], last[N];
int root[N], tot;
int ls[N * 40], rs[N * 40], sum[N * 40];

void change(int& u, int v, int l, int r, int p, int k)
{
    u = ++tot;
    ls[u] = ls[v];
    rs[u] = rs[v];
    sum[u] = sum[v] + k;
    if (l == r) return;
    if (p <= mid) change(ls[u], ls[v], l, mid, p, k);
    else change(rs[u], rs[v], mid + 1, r, p, k);
}
int find(int u, int l, int r, int p)
{
    if (l == r) return sum[u];
    if (p <= mid) return find(ls[u], l, mid, p) + sum[rs[u]];
    else return find(rs[u], mid + 1, r, p);
}
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, rt; i <= n; i++)
    {
        if (!last[a[i]]) change(root[i], root[i - 1], 1, n, i, 1);
        else
        {
            change(rt, root[i - 1], 1, n, last[a[i]], -1);
            change(root[i], rt, 1, n, i, 1);
        }
        last[a[i]] = i;
    }
    cin >> m;
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        cout << find(root[r], 1, n, l) << '\n';
    }
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}