#include <bits/stdc++.h>
#define For(i, a, b) for (int i = a; i <= b; ++i)
#define Rep(i, a, b) for (int i = a; i >= b; --i)
using namespace std;
const int maxN = 1e5 + 5;
struct seg_tree {
	int tg, val;
}T[maxN << 2];
int n, m;
int st1[maxN], tp1, st2[maxN], tp2, a[maxN];
int al[maxN], ar[maxN];
struct Query {
	int l, r, id;
	bool operator< (const Query &a) const { return l < a.l; }
	bool operator== (const Query &a) const { return id == a.id; }
}qu[maxN];
inline void addt(int x, int v) { T[x].tg += v; T[x].val += v; }
inline void pd(int k) {
	if (T[k].tg) {
		addt(k << 1, T[k].tg); addt(k << 1|1, T[k].tg);
		T[k].tg = 0;
	}
}
void update(int x, int y, int v, int k = 1, int l = 1, int r = n) {
	if (x <= l && r <= y) return addt(k, v);
	pd(k);
	int mid = l + r >> 1;
	if (x <= mid) update(x, y, v, k << 1, l, mid);
	if (y > mid) update(x, y, v, k << 1|1, mid + 1, r);
	T[k].val = min(T[k << 1].val, T[k << 1|1].val);
}
int query(int x, int y, int k = 1, int l = 1, int r = n) {
	if (x <= l && r <= y) return T[k].val;
	pd(k);
	int mid = l + r >> 1, s = n + 1;
	if (x <= mid) s = min(s, query(x, y, k << 1, l, mid));
	if (y > mid) s = min(s, query(x, y, k << 1|1, mid + 1, r));
	return s;
}
inline int findp(int r) {
	int l = 1, ans = -1, mid;
	if (query(1, r)) return -1;
	while (l <= r) {
		mid = l + r >> 1;
		if (query(mid, r) == 0) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	return ans;
}
set<Query> S;
int main() {
	scanf("%d", &n);
	For (i, 1, n) scanf("%d", a + i);
	scanf("%d", &m);
	For (i, 1, m) {
		scanf("%d%d", &qu[i].l, &qu[i].r); qu[i].id = i;
	}
	sort(qu + 1, qu + m + 1, [](Query a, Query b) { return a.r < b.r; });
	int tp = 1;
	For (i, 1, n) {
		while (tp1 && a[st1[tp1]] > a[i]) {
			update(st1[tp1 - 1] + 1, st1[tp1], -a[i] + a[st1[tp1]]);
			--tp1;
		}
		st1[++tp1] = i;
		while (tp2 && a[st2[tp2]] < a[i]) {
			update(st2[tp2 - 1] + 1, st2[tp2], a[i] - a[st2[tp2]]);
			--tp2;
		}
		st2[++tp2] = i;
		if (i > 1) update(1, i - 1, -1);
		while (tp <= m && qu[tp].r == i) S.emplace(qu[tp++]);
		while (!S.empty()) {
			auto v = *S.rbegin();
			int u = findp(v.l);
			if (u == -1) break;
			if (v.id == 12) {
				puts("NO");
			}
			al[v.id] = u; ar[v.id] = i;
			S.erase(*S.rbegin());
		}
	}
	if (tp <= m) puts("A");
	For (i, 1, m) printf("%d %d\n", al[i], ar[i]);
	return 0;
}