// codeforces 765F#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<vector>#include<cmath>#include<ctime>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std;const int maxn=300010;int n,Q,ans,a[maxn],res[maxn];struct data {int l,r,id;}q[maxn];struct node {int l,r,s;vector<int> v;}tr[maxn<<2];bool cmp(data a,data b) {return a.r<b.r;}void build(int k,int s,int t) {	tr[k].l=s;tr[k].r=t;tr[k].s=inf;	if (s==t) {tr[k].v.push_back(a[s]);return;}	int mid=(s+t)>>1;	build(k<<1,s,mid);build(k<<1|1,mid+1,t);	int i=0,j=0,ll=tr[k<<1].v.size(),rr=tr[k<<1|1].v.size();	while (i<ll || j<rr) {		if ((i<ll && tr[k<<1].v[i]<tr[k<<1|1].v[j]) || j==rr)			tr[k].v.push_back(tr[k<<1].v[i++]);		else tr[k].v.push_back(tr[k<<1|1].v[j++]);	}	for (int i=1;i<=t-s;i++) tr[k].s=min(tr[k].s,tr[k].v[i]-tr[k].v[i-1]);}int query(int k,int s,int t) {	int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;	if (l==s && r==t) return tr[k].s;	if (t<=mid) return query(k<<1,s,t);	else if (s>mid) return query(k<<1|1,s,t);	else return min(query(k<<1,s,mid),query(k<<1|1,mid+1,t));}void modify(int k,int p,int val) {	int l=tr[k].l,r=tr[k].r,mid=(l+r)>>1;	if (l==r) {tr[k].s=min(tr[k].s,abs(val-tr[k].v[0]));ans=min(ans,tr[k].s);return;}	vector<int>::iterator t=lower_bound(tr[k].v.begin(),tr[k].v.end(),val);	if (t==tr[k].v.end() || *t-val>=ans)		if (t==tr[k].v.begin() || val-*--t>=ans) {ans=min(ans,tr[k].s);return;}	if (p<=mid) modify(k<<1,p,val);	else modify(k<<1|1,p,val),modify(k<<1,p,val);	tr[k].s=min(tr[k].s,min(tr[k<<1].s,tr[k<<1|1].s));}int main() {	scanf("%d",&n);	for (int i=1;i<=n;i++) scanf("%d",&a[i]);	scanf("%d",&Q);	for (int i=1;i<=Q;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;	sort(q+1,q+1+Q,cmp);	build(1,1,n);	int p=1;	for (int i=1;i<=Q;i++) {		while (p<q[i].r) ans=inf,modify(1,p,a[p+1]),p++;		res[q[i].id]=query(1,q[i].l,q[i].r);	}	for (int i=1;i<=Q;i++) printf("%d\n",res[i]);	return 0;}