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

template <typename T> T& setmin(T& a, T b) { if (b < a) a = b; return a; }

const int INF = 1e9;

const int MAXN = 1.1e5;
const int MAXQ = 3.1e5;

struct seg_node {
	vector<int> vals;
	int minDiff;
} seg[1<<18];

int A[MAXN];

void build(int i, int l, int r) {
	seg[i].vals.reserve(r-l);
	if (l+1 == r) {
		seg[i].vals.push_back(A[l]);
	} else {
		int m = (l+r)/2;
		build(2*i, l, m);
		build(2*i+1, m, r);
		merge(seg[2*i].vals.begin(), seg[2*i].vals.end(), 
				seg[2*i+1].vals.begin(), seg[2*i+1].vals.end(), back_inserter(seg[i].vals));
	}
	assert(r-l == int(seg[i].vals.size()));
	assert(is_sorted(seg[i].vals.begin(), seg[i].vals.end()));
	seg[i].minDiff = INF;
	for (int z = 0; z+1 < int(seg[i].vals.size()); z++) {
		setmin(seg[i].minDiff, seg[i].vals[z+1] - seg[i].vals[z]);
	}
}

int query(int i, int l, int r, int ql, int qr) {
	if (qr <= l || r <= ql) {
		return INF;
	} else if (ql <= l && r <= qr) {
		return seg[i].minDiff;
	} else {
		int m = (l+r)/2;
		return min(query(2*i, l, m, ql, qr), query(2*i+1, m, r, ql, qr));
	}
}

void update(int i, int l, int r, int qr, int v, int& d) {
	if (qr <= l) return;
	if (l+1 == r) {
		setmin(seg[i].minDiff, abs(A[l]-v));
		setmin(d, abs(A[l]-v));
	} else {
		auto it = lower_bound(seg[i].vals.begin(), seg[i].vals.end(), v);
		// doesn't optimize
		if ((it == seg[i].vals.end() || v+d <= *it) && 
				(it == seg[i].vals.begin() || *prev(it) <= v-d)) {
			return;
		}
		int m = (l+r)/2;
		update(2*i+1, m, r, qr, v, d);
		update(2*i, l, m, qr, v, d);
		setmin(seg[i].minDiff, min(seg[2*i].minDiff, seg[2*i+1].minDiff));
	}
}

int ans[MAXQ];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];

	int Q; cin >> Q;
	vector<vector<pair<int, int>>> queries(N);
	for (int q = 0; q < Q; q++) {
		int l, r; cin >> l >> r; l--, r--;
		assert(r >= 1);
		queries[r].emplace_back(l, q);
	}
	
	build(1, 0, N);
	for (int i = 1; i < N; i++) {
		int tmp = INF;
		update(1, 0, N, i, A[i], tmp);
		for (auto it : queries[i]) {
			int l = it.first;
			int q = it.second;
			ans[q] = query(1, 0, N, l, i+1);
		}
	}

	for (int q = 0; q < Q; q++) { cout << ans[q] << '\n'; }

	return 0;
}