做法详见tj1.

#include<bits/stdc++.h>
#define int long long
#define I using
#define AK namespace
#define NOIP2024 std
I AK NOIP2024;
const int maxn=1e5+10,inf=1e18;
int n,q,l,r,tot,arr[maxn],tag[maxn];
struct rec
{
	int val,id;
	bool operator<(rec x)const
	{
		return(val==x.val)?(id<x.id):(val<x.val);
	}
}flag[maxn];
struct node
{
	int val,l,r;
}ans[maxn*10];
bool cmp(node x,node y)
{
	if(x.val==y.val)
	{
		return x.l<y.l;
	}
	return x.val<y.val;
}
signed main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>arr[i];
		flag[i]={arr[i],i};
	}
	sort(flag+1,flag+n+1);
	for(int i=1;i<n;i++)
	{
		for(int j=i+1;j<=min(n,i+10);j++)
		{
			ans[++tot]={abs(flag[j].val-flag[i].val),min(flag[i].id,flag[j].id),max(flag[i].id,flag[j].id)};
		}
	}
	sort(ans+1,ans+tot+1,cmp);
	while(q--)
	{
		int qwq=inf,cnt=0;
		cin>>l>>r;
		for(int i=1;i<=2000;i++)
		{
			if(l<=ans[i].l and r>=ans[i].r)
			{
			    cout<<ans[i].val<<"\n";
				goto loop;
			}
		}
		for(int i=l;i<=r;i++)
        {
        	tag[++cnt]=arr[i];
		}
        sort(tag+1,tag+cnt+1);
        for(int i=2;i<=cnt;i++)
        {
        	if(tag[i]!=tag[i-1])
        	{
        		qwq=min(qwq,abs(tag[i]-tag[i-1]));
			}
		}
        cout<<qwq<<"\n";
		loop:;
	}
	return 0;
}