#include<bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << #x << " = " << x << '\n';
#ifndef LOCAL
    #define cerr if(0) cerr
#endif
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mkt make_tuple
#define forn(i, n) for(int i = 0; i < int(n); i++)
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;

const ld eps = 1e-8;
const ld Pi = acosl(-1);
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
const ll INFL = 9e18;

void solve();
int main()
{
    cout.sync_with_stdio(0);
    cout.tie(0);
    cout.precision(0);
    cout << fixed;
    int t = 1;
    #ifdef LOCAL
    	assert(freopen("in", "r", stdin));
		freopen("out", "w", stdout);
		freopen("err", "w", stderr);
		cin >> t;
    #endif

    while(t--)
        solve();
}

void solve()
{
	int n;
	cin >> n;
	vi h(n);
	for (int& i: h) {
		cin >> i;
	}

	vi hused = h;
	sort(all(hused));
	for (int& i: h) {
		i = lower_bound(all(hused), i) - hused.begin();
	}

	int m;
	cin >> m;
	vector<tuple<int, int, int>> q(m);
	forn (i, m) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		q[i] = mkt(a, b, i);
	}
	const int K = 300;
	sort(all(q), [&](tuple<int, int> a, tuple<int, int> b) {
		int x1, y1, x2, y2;
		tie(x1, y1) = a;
		tie(x2, y2) = b;
		return mkt(x1 / K, y1) < mkt(x2 / K, y1);
	});

	int cl = 0, cr = -1;
	set<tuple<int, int, int>> answ;
	vector<tuple<int, int>> av(m, mkt(-1, -1));

	forn (i, m) {
		int l, r, id;
		tie (l, r, id) = q[i];
		while (cl < l) {

		}

		while (cr > r) {

		}

		while (!answ.empty()) {
			int la, ra, val;
			tie (val, la, ra) = *answ.begin();
			if (la >= l && ra <= r) {
				av[id] = val;
				break;
			}
			answ.erase(answ.begin());
		}
	}
}