学步园

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000001;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x*f;
}
const int N = 50005;
int n, m, l = 1, mx, a[N], next[N], t[N], p[1000001];

struct data {
    int l, r, id, ans;
} q[4 * N];

inline bool cmp1(data a, data b) {
    return a.l == b.l ? a.r < b.r : a.l < b.l;
}

inline bool cmp2(data a, data b) {
    return a.id < b.id;
}

inline void update(int x, int v) {
    for (int i = x; i <= n; i += i & (-i))
        t[i] += v;
}

inline int ask(int x) {
    int res = 0;
    for (int i = x; i; i -= i & (-i))
        res += t[i];
    return res;
}

int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        mx = max(a[i], mx);
    }
    for (int i = n; i; i--) {
        next[i] = p[a[i]];
        p[a[i]] = i;
    }
    for (int i = mx; i; i--)
        if (p[i])update(p[i], 1);
    m = read();
    for (int i = 1; i <= m; i++) {
        q[i].l = read();
        q[i].r = read();
        q[i].id = i;
    }
    sort(q + 1, q + m + 1, cmp1);
    for (int i = 1; i <= m; i++) {
        while (l < q[i].l) {
            if (next[l])update(next[l], 1);
            l++;
        }
        q[i].ans = ask(q[i].r) - ask(q[i].l - 1);
    }
    sort(q + 1, q + m + 1, cmp2);
    for (int i = 1; i <= m; i++)
        printf("%d\n", q[i].ans);
    return 0;
}