#include <bits/stdc++.h>
using namespace std;

#define QwQ330AwA return 0

const int N = 1e5 + 5;
int n;
int w[N];
int smx[N], smn[N], tmx, tmn;
struct Tree {
	int mn;
	int s;
	int tag;
} t[N << 2];

#define ls (p << 1)
#define rs ((p << 1)| 1)

void push(int p, int w) {
	t[p].mn += w;
	t[p].tag += w;
}

void pushup(int p) {
	t[p].mn = min(t[ls].mn, t[rs].mn);
	t[p].s = 0;
	if (t[p].mn == t[ls].mn) t[p].s += t[ls].s;
	if (t[p].mn == t[rs].mn) t[p].s += t[rs].s;
}

void pushdown(int p) {
	push(ls, t[p].tag);
	push(rs, t[p].tag);
	t[p].tag = 0;
}

void build(int p, int l, int r) {
	t[p].s = r - l + 1;
	if (l == r) return ;
	int mid = (l + r) / 2;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	pushup(p);
}

void update(int p, int l, int r, int L, int R, int w) {
	if (L <= l && r <= R) {
		push(p, w);
		return ;
	}
	pushdown(p);
	int mid = (l + r) / 2;
	if (L <= mid) update(ls, l, mid, L, R, w);
	if (mid < R) update(rs, mid + 1, r, L, R, w);
	pushup(p);
}

int query(int p, int l, int r, int L, int R) {
	if (l == r) {
//		cout << l << endl;
		if (t[p].mn == -1) return l;
		else return -330;
	}
	pushdown(p);
	int mid = (l + r) / 2;
	if (L <= l && r <= R) {
		if (t[rs].mn == -1) return query(rs, mid + 1, r, L, R);
		else if (t[ls].mn == -1) return query(ls, l, mid, L, R);
		else return -330;
	}
	if (mid < R) {
		int ans = query(rs, mid + 1, r, L, R);
		if (ans != -330) return ans;
	}
	if (L <= mid) {
		int ans = query(ls, l, mid, L, R);
		if (ans != -330) return ans;		
	}
	return -330;
}

struct Node {
	int l, id;
	bool operator < (const Node rhs) const {
		return l < rhs.l;
	}
};

priority_queue <Node> q;
pair <int, int> ans[N];
int m;
vector <Node> ask[N];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> w[i];
	cin >> m;
	for (int i = 1, l, r; i <= m; i++) {
		cin >> l >> r;
		ask[r].push_back({l, i});
	}
	build(1, 1, n);
	for (int i = 1; i <= n; i++) {
		while (tmx && w[smx[tmx]] < w[i]) update(1, 1, n, smx[tmx - 1] + 1, smx[tmx], -w[smx[tmx]]), tmx--;
		while (tmn && w[smn[tmn]] > w[i]) update(1, 1, n, smn[tmn - 1] + 1, smn[tmn], w[smn[tmn]]), tmn--;
		update(1, 1, n, 1, i, -1);
		smx[++tmx] = i;
		smn[++tmn] = i;
		update(1, 1, n, smx[tmx - 1] + 1, i, w[i]);
		update(1, 1, n, smn[tmn - 1] + 1, i, -w[i]);			
		for (auto qwq : ask[i]) q.push(qwq);
		while (!q.empty()) {
			int lim = q.top().l;
//			cout << lim << endl;
			int now = query(1, 1, n, 1, lim);
			if (now == -330) break;
			ans[q.top().id] = {now, i};
			q.pop();
		}
	}
	for (int i = 1; i <= m; i++) cout << ans[i].first << ' ' << ans[i].second << '\n';
	QwQ330AwA;
}