思路就是分块，小对小归并，小对大对整块处理每个值到此块的答案并计算块内的前缀/后缀，大对大预处理。

已知 RE 在了求 pre 和 suf 处即 40~47 行，眼睛调瞎了，悬赏三个关注~

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=1e5+10;
const int mod=1e9+7;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int B=300;
const int LEN=maxn/B+5;
int n,m,a[maxn],b[maxn],c[maxn],lft[LEN],rht[LEN],bel[maxn],Mn[LEN][LEN];
int tmp[maxn],top,bot[maxn],pre[B+5][maxn],suf[B+5][maxn];
struct node{int x,id;bool operator<(node y){return x<y.x;}}d[maxn];
int main(){
	n=read();int blo=0;
	//assert(0);
	for(int i=1;i<=n;i++)a[i]=b[i]=c[i]=read();
	sort(c+1,c+1+n);c[0]=unique(c+1,c+1+n)-c-1;
	for(int i=1;i<=n;i++)
		a[i]=b[i]=lower_bound(c+1,c+1+c[0],a[i])-c;
	for(int i=1;;i++){
		lft[i]=rht[i-1]+1;
		rht[i]=min(lft[i]+B-1,n);
		for(int j=lft[i];j<=rht[i];j++)bel[j]=i,d[j]=(node){a[j],j};
		sort(b+lft[i],b+rht[i]+1);
		int Min=inf;sort(d+lft[i],d+rht[i]+1);
		for(int j=lft[i]+1;j<=rht[i];j++)Min=min(Min,c[b[j]]-c[b[j-1]]);
		Mn[i][i]=Min;
		if(rht[i]==n){blo=i;break;}
	}//if(n==100000)return 0;
	for(int i=1;i<=blo;i++){
		for(int j=1;j<=b[lft[i]];j++)bot[j]=c[b[lft[i]]]-c[j];
		for(int j=b[rht[i]];j<=c[0];j++)bot[j]=c[j]-c[b[rht[i]]];
		for(int j=lft[i];j<rht[i];j++)
			for(int k=b[j];k<=b[j+1];k++)bot[k]=min(c[k]-c[b[j]],c[b[j+1]]-c[k]);
		//
		for(int j=1;j<=n;j++){
			pre[i][j]=bot[a[j]];
			if(j!=lft[bel[j]])pre[i][j]=min(pre[i][j],pre[i][j-1]);
		}//if(n==100000)continue;
		for(int j=n;j>=1;j--){
			suf[i][j]=bot[a[j]];
			if(j!=rht[bel[j]])suf[i][j]=min(suf[i][j],suf[i][j+1]);
		}
	}
//	for(int i=1;i<=n;i++)
//		printf("%d ",bel[i]);puts("");
//	for(int i=1;i<=blo;i++,puts("")){
//		for(int j=1;j<=n;j++)
//			printf("%d ",pre[i][j]);puts("");
//		for(int j=1;j<=n;j++)
//			printf("%d ",suf[i][j]);puts("");
//	}
	if(n==100000)return 0;
	for(int len=2;len<=blo;len++)
		for(int l=1;l+len-1<=blo;l++){
			int r=l+len-1,res=inf;
			Mn[l][r]=min(suf[l][lft[r]],min(Mn[l][r-1],Mn[l+1][r]));
//			printf("Mn[%d][%d]=%d\n",l,r,Mn[l][r]);
		}
//	for(int i=1;i<=n;i++)printf("%d ",b[i]);puts("");
//	for(int i=1;i<=n;i++)
//		printf("%d %d\n",d[i].x,d[i].id);puts("");
	if(n==100000)return 0;
	m=read();
	while(m--){
		int l=read(),r=read(),res=inf;
		if(bel[l]==bel[r]){
			for(int i=lft[bel[l]],las=-inf;i<=rht[bel[l]];i++)
				if(d[i].id>=l&&d[i].id<=r)res=min(res,c[b[i]]-las),las=c[b[i]];
			printf("%d\n",res);continue;
		}if(bel[l]+1<bel[r])res=Mn[bel[l]+1][bel[r]-1];
		for(int i=bel[l]+1;i<bel[r];i++)
			res=min(res,min(suf[i][l],pre[i][r]));
//		printf("res=%d\n",res);
		int bl=bel[l],br=bel[r],p1=lft[bl],p2=lft[br],las=-inf;
		while(p1<=rht[bl]||p2<=rht[br]){
			while(p1<=rht[bl]&&d[p1].id<l)p1++;
			while(p2<=rht[br]&&d[p2].id>r)p2++;
			if(p1>rht[bl]&&p2>rht[br])break;
//			printf("%d %d\n",p1,p2);
			if(p1>rht[bl]||(p2<=rht[br]&&b[p1]>b[p2]))res=min(res,c[b[p2]]-las),las=c[b[p2]],p2++;
			else res=min(res,c[b[p1]]-las),las=c[b[p1]],p1++;
			//printf("%d %d\n",p1,p2);
		}printf("%d\n",res);
	}
	return 0;
}