#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define sz(s) (int)(s).size()
#define all(s) s.begin(),s.end()

void Speed() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

template<typename T>
struct sparse_table {
    vector<vector<T>> sparseTable;
    using F = function<T(T, T)>;
    F merge;

    static int LOG2(int x) { //floor(log2(x))
        return 31 - __builtin_clz(x);
    }

    sparse_table() {}

    sparse_table(vector<T> &v, F merge) :
            merge(merge) {
        int n = v.size();
        int logN = LOG2(n);
        sparseTable = vector<vector<T>>(logN + 1);
        sparseTable[0] = v;
        for (int k = 1, len = 1; k <= logN; k++, len <<= 1) {
            sparseTable[k].resize(n);
            for (int i = 0; i + len < n; i++)
                sparseTable[k][i] = merge(sparseTable[k - 1][i],
                                          sparseTable[k - 1][i + len]);
        }
    }

    T query(int l, int r) {
        r -= 2;
        if (l > r)return 0;
        int k = LOG2(r - l + 1); // max k ==> 2^k <= length of range
//check first 2^k from left and last 2^k from right //overlap
        return merge(sparseTable[k][l], sparseTable[k][r - (1 << k) + 1]);
    }

    T query_shifting(int l, int r) {
        T res;
        bool first = true;
        for (int i = (int) sparseTable.size() - 1; i >= 0; i--)
            if (l + (1 << i) - 1 <= r) {
                if (first)
                    res = sparseTable[i][l];
                else
                    res = merge(res, sparseTable[i][l]);
                first = false;
                l += (1 << i);
            }
        return res;
    }
};

sparse_table<int> sp;
const int N = 1e5 + 5;
int a[N];
deque<int> idx[N];
int freq[N];
priority_queue<int>curr;
struct Mo {
    int n, sq;

    Mo(int n) : n(n), sq(sqrt(n)) {}

    struct query {
        int l, r, id, block_id;

        query(int l, int r, int id, int sq) : l(l), r(r), id(id), block_id(l / sq) {}

        bool operator<(const query &other) const {
            if (block_id == other.block_id) return r < other.r;
            return block_id < other.block_id;
        }
    };

    vector<query> Q;

    void addQuery(int l, int r, int id) {
        Q.emplace_back(l, r, id, sq);
    }

    void add(int i, bool left) {
        if (!i)return;
        if (sz(idx[a[i]]) > 1) {
            int x = sp.query(idx[a[i]].front(), idx[a[i]].back());
            if (x > a[i])
                freq[x]--;
        }
        if (left)idx[a[i]].emplace_front(i);
        else idx[a[i]].emplace_back(i);
        if (sz(idx[a[i]]) > 1) {
            int x = sp.query(idx[a[i]].front(), idx[a[i]].back());
            if (x > a[i]) {
                if(!freq[x]++)curr.push(x);
            }
        }
    }

    void remove(int i, bool left) {
        if (!i)return;
        if (sz(idx[a[i]]) > 1) {
            int x = sp.query(idx[a[i]].front(), idx[a[i]].back());
            if (x > a[i])
                freq[x]--;
        }
        if (left)idx[a[i]].pop_front();
        else idx[a[i]].pop_back();
        if (sz(idx[a[i]]) > 1) {
            int x = sp.query(idx[a[i]].front(), idx[a[i]].back());
            if (x > a[i])
                if(!freq[x]++)curr.push(x);
        }
    }

    vector<int> process() {
        vector<int> ans(sz(Q));
        sort(all(Q));
        int curL = 0, curR = -1; // 1-based
        for (auto [l, r, id, block_Id]: Q) {
            while (curL > l) add(--curL, 1);
            while (curR < r) add(++curR, 0);
            while (curL < l) remove(curL++, 1);
            while (curR > r) remove(curR--, 0);
            while(freq[curr.top()]==0)curr.pop();
            ans[id] = curr.top();
        }
        return ans;
    }
};

void solve() {
    while(!curr.empty())curr.pop();
    curr.push(0);
    freq[0]=1;
    int n;
    cin >> n;
    vector<int> ord, v;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        ord.emplace_back(a[i]);
    }
    sort(all(ord));
    ord.erase(unique(all(ord)), ord.end());
    for (int i = 1; i <= n; i++) {
        int id = lower_bound(all(ord), a[i]) - ord.begin();
        a[i] = id + 1;
        v.emplace_back(a[i]);
    }
    sp = sparse_table<int>(v, [&](const int &a, const int &b) -> int {
        return max(a, b);
    });
    int q;
    cin >> q;
    Mo mo(n);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        mo.addQuery(l, r, i);
    }
    auto ans = mo.process();
    for (auto it: ans)cout << (it ? ord[it - 1] : 0) << '\n';
    for (auto it: v) {
        idx[it].clear();
        freq[it]=0;
    }
}

/*
 2
 4
 2 1 3 2
 2
 2 4
 1 4
 8
 1 10 2 3 2 6 3 6
 4
 1 5
 1 8
 3 6
 3 8



 */
int main() {
    Speed();
    int tc = 1;
    cin >> tc;
    while (tc--) {
        solve();
    }
    return 0;
}