#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
//#define int long long
const int INF=1e9+1;
const int N=1e5+10;
struct zyh{
	int pos,val;
}a[N];
int trans[N];
int lqr;
bool cmp1(zyh pre,zyh nxt){
	return pre.val<nxt.val;
}
bool cmp2(zyh pre,zyh nxt){
	return pre.pos<nxt.pos;
}
struct seg{
	int l,r,maxn,minn;
}tree[4*N];
struct node{
	int l,r;
}bl[405];
void build_t(int pos,int lft,int rgt){
	tree[pos].l=lft;
	tree[pos].r=rgt;
	tree[pos].maxn=-1;
	tree[pos].minn=INF;
	if(lft==rgt) return;
	int mid=(lft+rgt)/2;
	build_t(pos*2,lft,mid);
	build_t(pos*2+1,mid+1,rgt);
}
void upd(int pos,int dot,int x){
	if(dot<tree[pos].l||tree[pos].r<dot) return;
	tree[pos].maxn=max(tree[pos].maxn,x);
	tree[pos].minn=min(tree[pos].minn,x);
	upd(pos*2,dot,x);
	upd(pos*2+1,dot,x);
}
int ask1(int pos,int lft,int rgt){
	if(rgt<tree[pos].l||tree[pos].r<lft) return -INF;
	if(lft<=tree[pos].l&&tree[pos].r<=rgt) return tree[pos].maxn;
	return max(ask1(pos*2,lft,rgt),ask1(pos*2+1,lft,rgt));
}
int ask2(int pos,int lft,int rgt){
	if(rgt<tree[pos].l||tree[pos].r<lft) return INF;
	if(lft<=tree[pos].l&&tree[pos].r<=rgt) return tree[pos].minn;
	return min(ask2(pos*2,lft,rgt),ask2(pos*2+1,lft,rgt));
}
int bl_ans[405][405],p_bl[N][405],bl_p[405][N];
int n,m,len,cnt;
void read(int &x) {
	x=0;int f=1;
	char s=getchar();
	for(;s<'0'||s>'9';s=getchar()) f=s=='-'?-f:f;
	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
	x*=f;
}
int blo[N];
int premax[N],nxtmin[N];
void build(){
	len=sqrt(n);
	for(int i=1;i<=n;i+=len){
		cnt++;
		bl[cnt].l=i;
		bl[cnt].r=min(i+len-1,n);
		for(int j=bl[cnt].l;j<=bl[cnt].r;j++){
			blo[j]=cnt;
		}
	}
	for(int i=1;i<=cnt;i++){
		build_t(1,1,lqr);
		int tmp=INF,bn=i;
		for(int j=bl[i].l;j<=n;j++){
			tmp=min(tmp,min(a[j].val-ask1(1,1,trans[j]),ask2(1,trans[j],lqr)-a[j].val));
			if(j==bl[bn].r){
				bl_ans[i][bn]=tmp;
				bn++;
			}
			upd(1,trans[j],a[j].val);
		}
	}
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=lqr;j++){
			premax[j]=-1;
			nxtmin[j]=INF;
		}
		for(int j=bl[i].l;j<=bl[i].r;j++){
			premax[trans[j]]=nxtmin[trans[j]]=a[j].val;
		}
		for(int j=2;j<=lqr;j++){
			premax[j]=max(premax[j],premax[j-1]);
		}
		for(int j=lqr-1;j>0;j--){
			nxtmin[j]=min(nxtmin[j],nxtmin[j+1]);
		}
		for(int j=1;j<bl[i].l;j++){
			p_bl[j][i]=min(a[j].val-premax[trans[j]],nxtmin[trans[j]]-a[j].val);
		}
		for(int j=bl[i].r+1;j<=n;j++){
			bl_p[i][j]=min(a[j].val-premax[trans[j]],nxtmin[trans[j]]-a[j].val);
		}
	}
	for(int i=1;i<cnt;i++){
		for(int j=bl[i].r-1;j>=bl[i].l;j--){
			p_bl[j][i+1]=min(p_bl[j][i],p_bl[j+1][i+1]);
		}
	}
	for(int i=2;i<=cnt;i++){
		for(int j=bl[i].l+1;j<=bl[i].r;j++){
			bl_p[i-1][j]=min(bl_p[i-1][j-1],p_bl[i-1][j]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=blo[i]+2;j<=cnt;j++){
			p_bl[i][j]=min(p_bl[i][j],p_bl[i][j-1]);
		}
		for(int j=blo[i]-2;j>0;j--){
			bl_p[j][i]=min(bl_p[j][i],bl_p[j+1][i]);
		}
	}
}
bool cmp(int pre,int nxt){
	return pre<nxt;
}
int tarr[805];
int ask(int x,int y){
	int ql,qr,ans=INF;
	for(int i=cnt;i>0;i--){
		if(x>=bl[i].l){
			ql=i;
			break;
		}
	}
	for(int i=cnt;i>0;i--){
		if(bl[i].l<=y){
			qr=i;
			break;
		}
	}
	if(ql==qr){
		int sb=0;
		for(int i=x;i<=y;i++){
			tarr[++sb]=a[i].val;
		}
		sort(tarr+1,tarr+sb+1,cmp);
		for(int i=2;i<=sb;i++){
			ans=min(ans,tarr[i]-tarr[i-1]);
		}
		return ans;
	}
	if(ql+1<=qr-1){
		ans=min(ans,bl_ans[ql+1][qr-1]);
		ans=min(ans,min(p_bl[x][qr-1],bl_p[ql+1][y]));
	}
	int sb=0;
	for(int i=x;i<=bl[ql].r;i++){
		sb++;
		tarr[sb]=a[i].val;
	}
	for(int i=bl[qr].l;i<=y;i++){
		sb++;
		tarr[sb]=a[i].val;
	}
	sort(tarr+1,tarr+sb+1,cmp);
	for(int i=1;i<=sb;i++){
		if(i!=1) ans=min(ans,tarr[i]-tarr[i-1]);
	}
	return ans;
}
signed main(){
	memset(p_bl,0x3f,sizeof(p_bl));
	memset(bl_p,0x3f,sizeof(bl_p));
	memset(bl_ans,0x3f,sizeof(bl_ans));
	ios::sync_with_stdio(false);
	read(n);
	for(int i=1;i<=n;i++){
		read(a[i].val);
		a[i].pos=i;
	}
	sort(a+1,a+n+1,cmp1);
	for(int i=1;i<=n;i++){
		if(a[i].val!=a[i-1].val||i==1) lqr++;
		trans[a[i].pos]=lqr;
	}
	sort(a+1,a+n+1,cmp2);
	build();
	read(m);
	while(m--){
		int ll,rr;
		read(ll);read(rr);
		cout<<ask(ll,rr)<<'\n';
	}
	return 0;
}