#include <vector>
#include <functional>
#include <optional>
#include <iostream>
#include <set>
#define FAST_ALLOCATOR_MEMORY (230*1024*1024)
#include "optimization.h"

using namespace std;
using ll = long long;

template<typename T>
struct Monoid;

template<typename Mon>
struct ValidMonoid : private Mon {
    using value_type = typename Mon::value_type;
    using T = typename Mon::value_type;
    static_assert(std::is_same_v<decltype(Mon::compose(std::declval<T>(), std::declval<T>())), T>);
    static_assert(std::is_same_v<decltype(Mon::identity()), T>);
    using Mon::compose;
    using Mon::identity;
};


template<typename T>
struct Updater : Updater<Monoid<T>> {
    using valid = ValidMonoid<Monoid<T>>;
};

template<typename Upd>
struct ValidUpdater : private Upd {
    using value_type = typename Upd::value_type;
    using update_type = typename Upd::update_type;
    using T = typename Upd::value_type;
    using U = typename Upd::update_type;
    using valid = ValidMonoid<Upd>;
    static_assert(std::is_same_v<decltype(Upd::update(std::declval<T>(), std::declval<U>(),
                                                      std::declval<size_t>(), std::declval<size_t>())), T>);
    using Upd::update;
    using Upd::compose;
    using Upd::identity;
};

template<typename T>
struct Updater<Monoid<T>> : Monoid<T> {
    using M = Monoid<T>;
    using valid = ValidMonoid<M>;
    using value_type = typename M::value_type;
    using update_type = typename M::value_type;

    static value_type update(const value_type& a, const update_type& b, size_t l, size_t r) { return M::compose(a, b); }
};

template<typename T>
struct STOp {
    using composer = ValidMonoid<Monoid<T>>;
    using updater = ValidUpdater<Updater<T>>;
};

template<typename Op>
struct ValidSTOp : Op {
    using compose_valid = ValidMonoid<typename Op::composer>;
    using updater_valid = ValidUpdater<typename Op::updater>;
    static_assert(std::is_same_v<typename Op::composer::value_type, typename Op::updater::value_type>);
    using typename Op::composer;
    using typename Op::updater;
};

template<typename Operation>
class SegmentTree {
public:
    using Op = ValidSTOp<STOp<Operation>>;
    using Cm = ValidMonoid<typename Op::composer>;
    using Up = ValidUpdater<typename Op::updater>;
    using T = typename Cm::value_type;
    using U = typename Up::update_type;

    explicit SegmentTree(size_t n) : n(n) {
        data.resize(4 * n, Cm::identity());
        updates.resize(data.size(), Up::identity());
    }

    explicit SegmentTree(int n) : SegmentTree(static_cast<size_t>(n)) {}

    template<typename Cont>
    explicit SegmentTree(const Cont& cont) : SegmentTree(cont.size()) {
        build(cont, 1, 0, n);
    }

    T compute(size_t l, size_t r) {
        return compute(1, 0, n, l, r);
    }

    void applyToLeaf(size_t i, std::function<T(const T&, size_t, size_t)> f) {
        applyToLeaf(1, 0, n, i, std::move(f));
    }

    void applyToLeaf(size_t i, std::function<T(const T&)> f) {
        applyToLeaf(i, [f](const T& t, size_t l, size_t r){ return f(t); });
    }

    void set(size_t i, T x) {
        applyToLeaf(i, [&x](const T& y, size_t l, size_t r) { return x; });
    }

    void update(size_t i, U upd) {
        applyToLeaf(i, [this, &upd](const T& x, size_t l, size_t r) { return Up::update(x, upd, l, r); });
    }

    void update(size_t l, size_t r, U upd) {
        update(1, 0, n, l, r, upd);
    }

private:

    void check_bounds(size_t v, size_t vl, size_t vr, size_t l, size_t r) {
        assert(v < data.size());
        assert(vl <= n);
        assert(vr <= n);
        assert(l <= n);
        assert(r <= n);
    }

    T compute(size_t v, size_t vl, size_t vr, size_t l, size_t r) {
        check_bounds(v, vl, vr, l, r);
        if (disjoint(vl, vr, l, r)) return Cm::identity();
        if (embedded(vl, vr, l, r)) {
            return data[v];
        }
        size_t vm = mid(vl, vr);
        return Up::update(
                Cm::compose(
                compute(left(v), vl, vm, l, r),
                compute(right(v), vm, vr, l, r)
                ),
                updates[v], vl, vr
        );
    }

    void update(size_t v, size_t vl, size_t vr, size_t l, size_t r, U upd) {
        check_bounds(v, vl, vr, l, r);
        recompute(v, vl, vr);
        if (disjoint(vl, vr, l, r)) return;
        if (embedded(vl, vr, l, r)) {
            updates[v] = Up::compose(updates[v], upd);
            recompute(v, vl, vr);
            return;
        }
        size_t vm = mid(vl, vr);
        push(v);
        update(left(v), vl, vm, l, r, upd);
        update(right(v), vm, vr, l, r, upd);
        recompute(v, vl, vr);
    }

    void push(size_t v) {
        assert(v < data.size());
        updates[left(v)] = Up::compose(updates[left(v)], updates[v]);
        updates[right(v)] = Up::compose(updates[right(v)], updates[v]);
        updates[v] = Up::identity();
    }

    void applyToLeaf(size_t v, size_t vl, size_t vr, size_t i, std::function<T(const T&, size_t, size_t)> f) {
        check_bounds(v, vl, vr, 0, 0);
        if (vl == i && vr == i + 1) {
            data[v] = f(data[v], vl, vr);
            return;
        }
        size_t vm = mid(vl, vr);
        if (i < vm) applyToLeaf(left(v), vl, vm, i, f);
        else applyToLeaf(right(v), vm, vr, i, f);
        recompute(v, vl, vr);
    }

    template<typename Cont>
    void build(const Cont& cnt, size_t v, size_t vl, size_t vr) {
        if(vl + 1 == vr) {
            data[v] = cnt[vl];
            return;
        }
        size_t vm = mid(vl, vr);
        build(cnt, left(v), vl, vm);
        build(cnt, right(v), vm, vr);
        recompute(v, vl, vr);
    }

    bool disjoint(size_t vl, size_t vr, size_t l, size_t r) { return vr <= l || r <= vl; }

    bool embedded(size_t vl, size_t vr, size_t l, size_t r) { return l <= vl && vr <= r; }

    size_t mid(size_t vl, size_t vr) { return (vl + vr + 1) / 2; }

    size_t left(size_t i) { return 2 * i; }

    size_t right(size_t i) { return 2 * i + 1; }

    void recompute(size_t i, size_t vl, size_t vr) {
        check_bounds(i, vl, vr, 0, 0);
        if(vl + 1 == vr) {
            data[i] = Up::update(data[i], updates[i], vl, vr);
            updates[i] = Up::identity();
        } else {
            data[i] = Up::update(
                    Cm::compose(data[left(i)], data[right(i)]),
                    updates[i], vl, vr
            );
        }
    }

    size_t n;
    std::vector<T> data;
    std::vector<U> updates;
};


template<typename T, T id = 0>
struct Sum {
};

template<typename T, T id>
struct Monoid<Sum<T, id>> {
    using value_type = T;

    static T identity() { return id; };

    static T compose(T a, T b) {
        return a + b;
    }
};

template<typename T, T id>
struct Updater<Sum<T, id>> : Monoid<Sum<T, id>> {
    using update_type = T;

    static T update(T x, T up, size_t l, size_t r) {
        return x + up * (r - l);
    }
};

template<typename T, T id = std::numeric_limits<T>::max()>
struct Min {
};

template<typename T, T id>
struct Monoid<Min<T, id>> {
    using value_type = T;

    static T identity() { return id; };

    static T compose(T a, T b) {
        return min(a, b);
    }
};

template<typename T, const T* id = &std::numeric_limits<T>::min()>
struct Max {
};

template<typename T, const T* id>
struct Monoid<Max<T, id>> {
    using value_type = T;

    static T identity() { return *id; };

    static T compose(T a, T b) {
        return max(a, b);
    }
};

//template<typename T, T* id>
//struct Updater<Max<T, id>> : Monoid<Max<T, id>> {
//
//    using value_type = T;
//    using update_type = T;
//
//    static value_type update(value_type a, update_type b, size_t l, size_t r) {
//        return max(a, b);
//    }
//
//};

template<typename T, T id = 0>
struct PureSum {
};

template<typename T, T id>
struct Updater<PureSum<T, id>> : Monoid<Sum<T, id>> {
    using update_type = T;

    static T update(const T& a, const T& b, size_t l, size_t r) { return a + b; }

};

struct CountSegments {};

struct CSNode {
    enum class Color {
        BLACK,
        WHITE
    };

    Color beg, end;
    size_t black_cnt, len;
};

std::string to_str(CSNode::Color c) {
    return c == CSNode::Color::BLACK ? "B" : "W";
}
bool debug = false;
template<>
struct Monoid<CountSegments> {
    using value_type = CSNode;
    using Color = CSNode::Color;
    static value_type identity() {
        return {Color::WHITE, Color::WHITE, 0, 0};
    }

    static value_type compose(value_type a, value_type b) {
        CSNode res = {a.beg, b.end, a.black_cnt + b.black_cnt - (a.end == Color::BLACK && b.beg == Color::BLACK), a.len + b.len};
        if(debug)
        std::cerr << "Composing "
                  << to_str(a.beg) << "[" << a.black_cnt << "]" << to_str(a.end)
                  << " with "
                  << to_str(b.beg) << "[" << b.black_cnt << "]" << to_str(b.end)
                  << " result "
                  << to_str(res.beg) << "[" << res.black_cnt << "]" << to_str(res.end)
                  << std::endl;
        return res;
    }
};


template<>
struct Updater<CountSegments> {

    using value_type = CSNode;
    using update_type = std::optional<CSNode::Color>;

    static update_type identity() {
        return std::optional<CSNode::Color>();
    }

    static update_type compose(update_type a, update_type b) {
        if(!b.has_value()) return a;
        return b;
    }

    static value_type update(value_type a, update_type u, size_t l, size_t r) {
        if(!u.has_value()) return a;
        CSNode res = {u.value(), u.value(), u.value() == CSNode::Color::BLACK, u.value() == CSNode::Color::BLACK ? (r - l) : 0};
        if(debug)
            std::cerr << "Updating "
                      << to_str(a.beg) << "[" << a.black_cnt << "]" << to_str(a.end)
                      << " to "
                      << to_str(res.beg) << "[" << res.black_cnt << "]" << to_str(res.end)
                      << std::endl;
        return res;
    }
};

struct RectUpdater;

template<>
struct Updater<RectUpdater> : Monoid<Sum<int>> {

    using value_type = pair<int, int>;
    using update_type = int;

    static value_type update(value_type rect, update_type k, size_t l, size_t r) {
        return {rect.first + k, rect.second};
    }
};

struct CountDisting {};

template<>
struct Monoid<CountDisting> {
    using value_type = set<int>;

    static value_type identity() {
        return set<int>();
    }

    static value_type compose(value_type a, value_type b) {
        set<int> res;
        res.insert(a.begin(), a.end());
        res.insert(b.begin(), b.end());
        return res;
    }
};

template<typename T>
struct NoUpdates {};

template<typename T>
struct Updater<NoUpdates<T>> {
    using value_type = T;
    using update_type = char;

    static update_type identity() {
        return 0;
    }

    static update_type compose(update_type a, update_type b) {
        return 0;
    }

    static value_type update(value_type a, update_type b, size_t l, size_t r) {
        return a;
    }
};

template<typename Op, typename Up>
struct ComplexOp {
};

template<typename Op, typename Up>
struct STOp<ComplexOp<Op, Up>> {
    using composer = ValidMonoid<typename STOp<Op>::composer>;
    using updater = ValidUpdater<typename STOp<Up>::updater>;
};

using sum_type = size_t;

constexpr pair<sum_type, int> identity{0, -1};

int main() {
    int n = readInt();
    std::vector<set<int>> data;
    data.reserve(n);
    for (int i = 0; i < n; ++i) {
        data.push_back(set<int>{readInt()});
    }
    SegmentTree<ComplexOp<CountDisting, NoUpdates<set<int>>>> tree(data);
    int k = readInt();
    std::vector<std::tuple<int, int, int>> events;
    for (int i = 0; i < k; ++i) {
        int l = readInt(), r = readInt();
        writeInt(tree.compute(l - 1, r).size(), '\n');
    }
}

//int main() {
//    int n = readInt();
//    std::vector<std::tuple<int, int, int, int, int, int>> events;
//    for (int i = 0; i < n; ++i) {
//        int x1 = readInt(), y1 = readInt(), x2 = readInt(), y2 = readInt(), k = readInt();
//        events.emplace_back(x1, 0, y1, y2, k, i);
//        events.emplace_back(x2, 2, y1, y2, k, i);
//    }
//    sort(events.begin(), events.end());
//    std::vector<int> coords{(int) -2e9, (int) 2e9};
//    for (auto [x, type, y1, y2, k, i] : events) {
//        coords.push_back(y1 - 1);
//        coords.push_back(y1 * 1);
//        coords.push_back(y2 * 1);
//    }
//    sort(coords.begin(), coords.end());
//    coords.erase(unique(coords.begin(), coords.end()), coords.end());
//    std::vector<pair<sum_type, int>> rects(n);
//    size_t N = coords.size();
//    SegmentTree<Max<pair<sum_type, int>, &identity>> tree(N);
//    for(auto [x, type, y1, y2, k, i] : events) {
//        y1 = lower_bound(coords.begin(), coords.end(), y1) - coords.begin();
//        y2 = lower_bound(coords.begin(), coords.end(), y2) - coords.begin();
//        switch(type) {
//            case 0: {
//                rects[i] = tree.compute(y2, N); //y2_new < y1_old
//                rects[i].first += k;
//                break;
//            }
//            case 2: {
//                tree.update(y1 - 1, y1, {rects[i].first, i});
//                break;
//            }
//        }
//    }
//    int maxI = 0;
//    for (int i = 0; i < n; ++i) {
//        if(rects[i].first > rects[maxI].first) {
//            maxI = i;
//        }
//    }
//    std::vector<int> chain;
//    for(int i = maxI; i != -1; i = rects[i].second) {
//        chain.push_back(i);
//    }
//    std::reverse(chain.begin(), chain.end());
//    writeInt(rects[maxI].first, '\n');
//    for(int i : chain) {
//        writeInt(i + 1, ' ');
//    }
//    writeChar('\n');
//}

// x1 y1 x2 y2
// a1 b1 a2 b2
// a1 > x2 && b2 < y1

//WWWWWWWWWWW
//WWWWWWWWWWW
//WWBBWWWWWWW
//WWBBBBWWWWW
//WWBBBBWWWWW
//WWBBBBWBBWW
//WWBWBBWBBWW
//WWWWWWWWWWW

//int main() {
//    int n = readInt();
//    int N = 1000002;
//    SegmentTree<CountSegments> tree(N);
//    for (int i = 0; i < n; ++i) {
//        debug = i == 5;
//        int color = readChar(), x = readInt(), l = readInt();
//        x += 500000;
//        tree.update(x, x+l, color == 'W' ? CSNode::Color::WHITE : CSNode::Color::BLACK);
//        CSNode ans = tree.compute(0, N);
//        writeInt(ans.black_cnt, ' ');
//        writeInt(ans.len, '\n');
//    }
//}

//int main() {
//    int n = readInt(), q = readInt();
//    vector<int> v;
//    v.reserve(n);
//    for (int i = 0; i < n; ++i) {
//        v.push_back(readInt());
//    }
//    SegmentTree<ComplexOp<Max<ll, static_cast<ll>(-1e15)>, PureSum<ll>>> tree(v);
//    for (int i = 0; i < q; ++i) {
//        int cmd = readChar();
//        readChar();
//        readChar();
//        int l = readInt() - 1, r = readInt();
//        if (cmd == 'm') {
//            writeInt(tree.compute(l, r), '\n');
//        } else {
//            int x = readInt();
//            tree.update(l, r, x);
//        }
//    }
//    return 0;
//}