rt，思路是跑莫队，用一个$set$存前后趋，优先队列存答案，WA一个RE四个

本地与暴力在$n<=1000$时对拍没问题怀疑数据有锅

#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#define int long long
using namespace std;
const int maxn=1e5+5;

struct Query
{
    int l,r,id,kl;
    inline bool operator < (const Query &a) const{
        return kl!=a.kl?kl<a.kl:(kl&1?r<a.r:r>a.r);
    }
}qu[maxn];

set<int> st;
priority_queue<int,vector<int>,greater<int> > insq,delq;
int vis[maxn],a[maxn],b[maxn],id[maxn],n,m,tt,istwo,nowans,ans[maxn];

template<typename T>
inline void read(T &x)
{
    char c;int f=1;
    while(!isdigit(c=getchar())) (c=='-')&&(f=-1);
    x=c^48;
    while(isdigit(c=getchar())) x=x*10+(c^48);
    x*=f;
}

inline void insque(int x)
{
    //cout<<'i'<<x<<endl;
    if(!delq.empty()&&delq.top()==x) delq.pop();
    else insq.push(x);
}

inline void delque(int x)
{
    //cout<<'d'<<x<<endl;
    if(!insq.empty()&&insq.top()==x) insq.pop();
    else delq.push(x);
}

inline int getque()
{
    while(!insq.empty()&&!delq.empty()&&insq.top()==delq.top()) insq.pop(),delq.pop();
    return insq.top();
}

inline void ins(int x)
{
    if(vis[id[x]]) {
        if(vis[id[x]]==1) istwo++;
        vis[id[x]]++;return;
    }
    vis[id[x]]++;
    if(st.empty()) {st.insert(a[x]);return;}
    set<int>::iterator f=st.lower_bound(a[x]);
    set<int>::iterator t=f;
    if(f!=st.begin()) f--;
    if(t==st.end()) t--;
    insque(abs(*f-a[x]));
    //if(st.size()==1) return;
    if(*f!=*t) insque(abs(a[x]-*t)),delque(abs(*f-*t));
    st.insert(a[x]);
    //
}

inline void del(int x)
{
    vis[id[x]]--;
    if(vis[id[x]]) {
        if(vis[id[x]]==1) istwo--;return;
    }
    st.erase(a[x]);
    if(st.empty()) return;
    //
    set<int>::iterator f=st.lower_bound(a[x]);
    set<int>::iterator t=f;
    if(f!=st.begin()) f--;
    if(t==st.end()) t--;
    delque(abs(*f-a[x]));
    //if(st.size()==1) return;
    if(*f!=*t) delque(abs(a[x]-*t)),insque(abs(*f-*t));
    //
}

signed main()
{
    read(n);read(m);
    int klen=n/sqrt(m*2/3);
    for(int i=1;i<=n;++i) read(a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    tt=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i)
        id[i]=lower_bound(b+1,b+tt+1,a[i])-b;
    for(int i=1;i<=m;++i)
    {
        read(qu[i].l);read(qu[i].r);
        qu[i].id=i;qu[i].kl=(qu[i].l-1)/klen+1;
    }
    sort(qu+1,qu+m+1);
    int l=1,r=0;
    for(int i=1;i<=m;++i)
    {
        while(r<qu[i].r) ins(++r);
        while(l>qu[i].l) ins(--l);
        while(l<qu[i].l) del(l++);
        while(r>qu[i].r) del(r--);
        if(istwo) ans[qu[i].id]=0;
        else ans[qu[i].id]=getque();
    }
    for(int i=1;i<=m;++i)
        printf("%d\n",ans[i]);
    return 0;
}