讨论区里，别发无意义内容，如果你没啥改进的想法或者你是 lxl ，就别说话。

//
// Created by XH on 2022/9/22.
//

#include <bits/stdc++.h>

using namespace std;

constexpr int S(int x) {
    return x + 2;
}

namespace io {
    const int IN_BUF = 1 << 16, OUT_BUF = 1 << 16; // IN_BUF 和 OUT_BUF 的值应确保缓冲区能卡进 L1 缓存
    char ibuf[IN_BUF], obuf[OUT_BUF], *i1, *i2, *o; // 因为 i1、i2 为全局变量，最开始全是 NULL ，满足 i1 == i2 。

    class init {
    public:
        init() {
            o = obuf;
        }

        ~init() {
            fwrite(obuf, o - obuf, sizeof(char), stdout);
        }
    } bminit;


    inline char gc() {
        if (__builtin_expect(i1 == i2, 0)) {
            i1 = ibuf;
            i2 = i1 + std::cin.rdbuf()->sgetn(ibuf, IN_BUF);
        }
        return i1 == i2 ? EOF : *i1++;
    }

    class fi {
    public:
        inline fi &operator>>(int &x) {
            char ch;
            bool flag = false;
            while (!isdigit(ch = gc()) && ch != EOF) {
                flag = ch == '-'; // 为了处理 "-  18" 这种情况，这时候输入的应为 18 而不是 -18。
            }
            for (x = 0; isdigit(ch); ch = gc()) {
                x = x * 10 + ch - '0';
            }
            if (flag) {
                x = -x;
            }
            return *this;
        }
    } cin;

    inline void pc(char ch) {
        if (__builtin_expect(o == obuf + OUT_BUF, 0)) {
            fwrite(obuf, OUT_BUF, sizeof(char), stdout);
            o = obuf;
        }
        *o++ = ch;
    }

    class fo {
    public:
        inline fo &operator<<(int x) { // 想输出 long long 将传参改为 long long x 即可。不能写成 const int &x ，因为 x 会被修改
            if (x < 0) {
                pc('-');
                x = -x;
            }
            static char s[20]; // LLONG_MAX 也只有 19 位，s 有 20 位，也能输出 long long
            int top = 0;
            do {
                s[top++] = x % 10;
                x /= 10;
            } while (x);
            while (top) {
                pc(s[--top] + '0');
            }
            return *this;
        }

        fo &operator<<(char c) {
            pc(c);
            return *this;
        }
    } cout;
}

namespace Main {
    using io::cin, io::cout;

    const int N = 1e6;
    const int V = 1e6;

    int a[S(N)], h[S(N)], ans[S(N)], res;
    unsigned char cnt[S(N)];
    tuple<int, int, int> q[S(N)];

    inline int clz(int x) {
        return __builtin_clz(x);
    }

    inline void plus(int i) {
        if (cnt[a[i]]++ == 0) {
            res++;
        }
    }

    inline void minus(int i) {
        if (--cnt[a[i]] == 0) {
            res--;
        }
    }

    void main() {
        int n, m, x, y;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        int cnt2[S(N)], mp[S(N)];
        memset(cnt2, 0, sizeof(cnt2));
        memset(mp, 0, sizeof(mp));
        for (int i = 1; i <= n; ++i) {
            ++cnt2[a[i]];
        }
        for (int i = 1; i <= V; ++i) {
            cnt2[i] >>= 1;
        }
        int k = 0;
        for (int i = 1; i <= n; ++i) {
            if (cnt2[a[i]]-- == 0) {
                mp[a[i]] = ++k;
            }
        }
        for (int i = 1; i <= n; ++i) {
            a[i] = mp[a[i]];
        }
        cin >> m;
        for (int i = 1; i <= m; ++i) {
            cin >> x >> y;
            q[i] = {x, y, i};
        }
//        /* 分块
        int len = ceil(1.425 * n / sqrt(m));
        sort(q + 1, q + m + 1, [&](auto x, auto y) {
            auto[a, b, c] = x;
            auto[d, e, f] = y;
            a /= len;
            d /= len;
            return a < d || (a == d && (a & 1 ? b < e : b > e));
        });
//         */
        /* z-order
        sort(q + 1, q + m + 1, [&](auto x, auto y) {
            auto[a, b, _1] = x;
            auto[c, d, _2] = y;
            a--;
            b--;
            c--;
            d--;
            if (a == c) {
                return b < d;
            }
            if (a < c) {
                if (b <= d) {
                    return true;
                } else {
                    return clz(c) <= clz(b);
                }
            } else {
                if (b >= d) {
                    return false;
                } else {
                    return clz(a) > clz(d);
                }
            }
        });
//        for (int i = 1; i <= m; ++i) {
//            auto[l, r, id] = q[i];
//            cerr << l << ' ' << r << ' ' << id << endl;
//        }
         */
        q[0] = {1, 1, 0};
        plus(1);
        int i = 1, j = 1;
        for (int o = 1; o <= m; ++o) {
            auto[l, r, id] = q[o];
            while (l < i) {
                plus(--i);
            }
            while (j < r) {
                plus(++j);
            }
            while (i < l) {
                minus(i++);
            }
            while (r < j) {
                minus(j--);
            }
            ans[id] = res;
        }
        for (int i = 1; i <= m; ++i) {
            cout << ans[i] << '\n';
        }
    }
}

int main() {
    Main::main();
    return 0;
}