过了 CF765F，但这题被卡常了，怎么会逝呢？

#include<bits/stdc++.h>
#define mkp make_pair
#define fir first
#define sec second
#define int long long
using namespace std;
const int N=3e5+10,M=1e6+10;
int n,m,ind,rt,a[N],out[M],t[N];
int ls[N*4],rs[N*4],mx[N*4];
vector<pair<int,int> > v[N];
void add(int x,int y)
{
	for(int i=x;i;i-=i&(-i))
	{
		t[i]=min(t[i],y);
	}
}
int ask(int x)
{
	int ret=2e9;
	for(int i=x;i<=n;i+=i&(-i))
	{
		ret=min(ret,t[i]);
	}
	return ret;
}
void update(int &p,int l,int r,int x,int y)
{
	if(!p)
	{
		p=++ind;
	}
	mx[p]=max(mx[p],y);
	if(l==r)
	{
		return;
	}
	int mid=(l+r)/2;
	if(x<=mid)
	{
		update(ls[p],l,mid,x,y);
	}else
	{
		update(rs[p],mid+1,r,x,y);
	}
}
int query(int p,int l,int r,int nl,int nr)
{
	if(!p)
	{
		return 0;
	}
	if(nl<=l&&r<=nr)
	{
		return mx[p];
	}
	int ret=0,mid=(l+r)/2;
	if(nl<=mid)
	{
		ret=max(ret,query(ls[p],l,mid,nl,nr));
	}
	if(nr>mid)
	{
		ret=max(ret,query(rs[p],mid+1,r,nl,nr));
	}
	return ret;
}
void work()
{
	int x;
	for(int i=1;i<=n;i++)
	{
		t[i]=2e9;
	}
	for(int i=1;i<=ind;i++)
	{
		ls[i]=rs[i]=mx[i]=0;
	}
	ind=rt=0;
	for(int i=1;i<=n;i++)
	{
		x=query(rt,1,2e9,a[i],2e9);
		while(x)
		{
			add(x,a[x]-a[i]);
			x=query(rt,1,2e9,a[i],(a[i]+a[x])/2-(~(a[i]+a[x])&1));
		}
		update(rt,1,2e9,a[i],i);
		for(auto j:v[i])
		{
			out[j.fir]=min(out[j.fir],ask(j.sec));
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int x,y;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		out[i]=2e9;
		v[y].push_back(mkp(i,x));
	}
	work();
	for(int i=1;i<=n;i++)
	{
		a[i]=2e9-a[i];
	}
	work();
	for(int i=1;i<=m;i++)
	{
		cout<<out[i]<<"\n";
	}
}