#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 100005;
const int LEN = 320;
const int NUM = 320;
struct Num {
	int val, i;
} b[N];
bool operator < (const Num & a, const Num & b) {
	return a.val < b.val;
}
int n, m, len, num, a[N], blo_l[NUM], blo_r[NUM], f[N][NUM], g[N][NUM], s[NUM][NUM];
int get_blo(int i) {
	return (i - 1) / len + 1;
}
int temp1[LEN], len1, temp2[LEN], len2;
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		b[i].val = a[i];
		b[i].i = i;
	}
	len = sqrt(n);
	num = get_blo(n);
	for (int i = 1; i <= num; i++) {
		blo_l[i] = blo_r[i - 1] + 1;
		blo_r[i] = blo_r[i - 1] + len;
	}
	blo_r[num] = n;
	for (int i = 1; i <= num; i++) {
		sort(b + blo_l[i], b + blo_r[i] + 1);
	}
	for (int i = 1; i <= num; i++) {
		for (int j = i + 1; j <= num; j++) {
			for (int k = blo_l[i], p = blo_l[j]; k <= blo_r[i]; k++) {
				while (p < blo_r[j] && b[k].val > b[p + 1].val) {
					p++;
				}
				f[b[k].i][j] = abs(b[k].val - b[p].val);
				if (p < blo_r[j]) {
					f[b[k].i][j] = min(f[b[k].i][j], abs(b[k].val - b[p + 1].val));
				}
			}
		}
		for (int j = i + 1; j <= num; j++) {
			for (int k = blo_r[i] - 1; k >= blo_l[i]; k--) {
				f[k][j] = min(f[k][j], f[k + 1][j]);
			}
		}
		for (int j = i + 2; j <= num; j++) {
			for (int k = blo_l[i]; k <= blo_r[i]; k++) {
				f[k][j] = min(f[k][j], f[k][j - 1]);
			}
		}
	}
	for (int i = 1; i <= num; i++) {
		for (int j = 1; j <= i - 1; j++) {
			for (int k = blo_l[i], p = blo_l[j]; k <= blo_r[i]; k++) {
				while (p < blo_r[j] && b[k].val > b[p + 1].val) {
					p++;
				}
				g[b[k].i][j] = abs(b[k].val - b[p].val);
				if (p < blo_r[j]) {
					g[b[k].i][j] = min(g[b[k].i][j], abs(b[k].val - b[p + 1].val));
				}
			}
		}
		for (int j = 1; j <= i - 1; j++) {
			for (int k = blo_l[i] + 1; k <= blo_r[i]; k++) {
				g[k][j] = min(g[k][j], g[k - 1][j]);
			}
		}
		for (int j = 1; j <= i - 2; j++) {
			for (int k = blo_l[i]; k <= blo_r[i]; k++) {
				g[k][j] = min(g[k][j], g[k][j + 1]);
			}
		}
	}
	for (int i = num; i >= 1; i--) {
		s[i][i] = 0x7fffffff;
		for (int j = blo_l[i]; j <= blo_r[i] - 1; j++) {
			s[i][i] = min(s[i][i], abs(b[j].val - b[j + 1].val));
		}
		for (int j = i + 1; j <= num; j++) {
			s[i][j] = min(s[i][j - 1], min(s[j][j], g[blo_r[j]][i]));
		}
	}
	scanf("%d", &m);
	for (int l, r, l_blo, r_blo, ans, last, i, j; m != 0; m--) {
		scanf("%d %d", &l, &r);
		l_blo = get_blo(l);
		r_blo = get_blo(r);
		ans = 0x7fffffff;
		if (l_blo == r_blo) {
			last = -1;
			for (int i = blo_l[l_blo]; i <= blo_r[l_blo]; i++) {
				if (l <= b[i].i && b[i].i <= r) {
					if (last == -1) {
						last = b[i].val;
					} else {
						ans = min(ans, b[i].val - last);
						last = b[i].val;
					}
				}
			}
		} else {
			if (l_blo + 1 <= r_blo - 1) {
				ans = min(ans, s[l_blo + 1][r_blo - 1]);
				ans = min(ans, f[l][r_blo - 1]);
				ans = min(ans, g[r][l_blo + 1]);
			}
			len1 = 0;
			for (int i = blo_l[l_blo]; i <= blo_r[l_blo]; i++) {
				if (l <= b[i].i && b[i].i <= blo_r[l_blo]) {
					len1++;
					temp1[len1] = b[i].val;
				}
			}
			len2 = 0;
			for (int i = blo_l[r_blo]; i <= blo_r[r_blo]; i++) {
				if (blo_l[r_blo] <= b[i].i && b[i].i <= r) {
					len2++;
					temp2[len2] = b[i].val;
				}
			}
			i = j = 1;
			last = min(temp1[i], temp2[j]);
			if (temp1[i] < temp2[j]) {
				i++;
			} else {
				j++;
			}
			while (i <= len1 && j <= len2) {
				if (temp1[i] < temp2[j]) {
					ans = min(ans, temp1[i] - last);
					last = temp1[i];
					i++;
				} else {
					ans = min(ans, temp2[j] - last);
					last = temp2[j];
					j++;
				}
			}
			while (i <= len1) {
				ans = min(ans, temp1[i] - last);
				last = temp1[i];
				i++;
			}
			while (j <= len2) {
				ans = min(ans, temp2[j] - last);
				last = temp2[j];
				j++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

思路同 mrsrz 的题解。