从第8个测试点开始TLE，线下 $n=100000,m=300000$ 随机数据预处理和读入加起来不超过0.5s，询问部分用时7~8s，求卡常

#include<cstdio>
#include<algorithm>
#include<ctime>
constexpr int MAXN=100002,LEN_BLOCK=288;
int n,m,a[MAXN],id[MAXN],rk[MAXN],block_n;
int arr[(MAXN+LEN_BLOCK-1)/LEN_BLOCK][LEN_BLOCK],arr_tot[(MAXN+LEN_BLOCK-1)/LEN_BLOCK];
int mn[(MAXN+LEN_BLOCK-1)/LEN_BLOCK][LEN_BLOCK][LEN_BLOCK];
int mx[(MAXN+LEN_BLOCK-1)/LEN_BLOCK][LEN_BLOCK][LEN_BLOCK];
int res_in_block[(MAXN+LEN_BLOCK-1)/LEN_BLOCK][LEN_BLOCK][LEN_BLOCK];
short before[(MAXN+LEN_BLOCK-1)/LEN_BLOCK][MAXN],after[(MAXN+LEN_BLOCK-1)/LEN_BLOCK][MAXN];
inline int abs(int a)
{
    return a<0?-a:a;
}
inline int read()
{
    int m=0;
    char ch=getchar();
    while(ch>'9'||ch<'0')
        ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        m=(m<<3)+(m<<1)+(ch^48);
        ch=getchar();
    }
    return m;
}
inline bool cmp(int u,int v) {return a[u]<a[v];}
inline void chk_min(int& u,int v) {u>v?u=v:0;}
inline void chk_max(int& u,int v) {u<v?u=v:0;}
int main()
{
    // freopen("CF765F.in","r",stdin);
    // freopen("CF765F.out","w",stdout);
    // clock_t st=clock();
    n=read();
    block_n=(n+LEN_BLOCK-1)/LEN_BLOCK;
    for(int i=1;i<=n;i++)
        a[i]=read(),id[i]=i;
    // fprintf(stderr,"until input use time %.6lf seconds\n",double(clock()-st)/CLOCKS_PER_SEC);
    std::sort(id+1,id+1+n,cmp);
    for(int i=1;i<=n;i++)
        rk[id[i]]=i;
    for(int i=1;i<=n;i++)
    {
        int bel=(rk[i]-1)/LEN_BLOCK;
        arr[bel][arr_tot[bel]++]=i;
    }
    for(int i=0;i<block_n;i++)
    {
        for(int j=0;j<arr_tot[i];j++)
        {
            res_in_block[i][j][j]=2e9+7;
            for(int k=j+1;k<arr_tot[i];k++)
                res_in_block[i][j][k]=std::min(res_in_block[i][j][k-1],abs(a[arr[i][k]]-a[arr[i][j]]));
        }
        for(int j=arr_tot[i]-2;j>=0;j--)
            for(int k=j+1;k<arr_tot[i];k++)
                chk_min(res_in_block[i][j][k],res_in_block[i][j+1][k]);
        for(int j=0;j<=n+1;j++)
            before[i][j]=-1,after[i][j]=32000;
        for(int j=0;j<arr_tot[i];j++)
        {
            mn[i][j][j]=mx[i][j][j]=a[arr[i][j]];
            for(int k=j+1;k<arr_tot[i];k++)
                mn[i][j][k]=std::min(mn[i][j][k-1],a[arr[i][k]]),
                mx[i][j][k]=std::max(mx[i][j][k-1],a[arr[i][k]]);
            before[i][arr[i][j]]=after[i][arr[i][j]]=j;
        }
        for(int j=n;j>=1;j--)
            if(after[i][j]==32000)
                after[i][j]=after[i][j+1];
        for(int j=1;j<=n;j++)
            if(before[i][j]==-1)
                before[i][j]=before[i][j-1];
    }
    // fprintf(stderr,"until pre processing use %.6lf seconds\n",double(clock()-st)/CLOCKS_PER_SEC);
    m=read();
    while(m--)
    {
        int l=read(),r=read(),res=2e9+7,cur_mx=-1;
        for(int i=0;i<block_n;i++)
        {
            int nl=after[i][l],nr=before[i][r];
            if(nl>nr) continue;
            if(cur_mx!=-1)
                chk_min(res,mn[i][nl][nr]-cur_mx);
            chk_min(res,res_in_block[i][nl][nr]);
            chk_max(cur_mx,mx[i][nl][nr]);
        }
        printf("%d\n",res);
    }
    // fprintf(stderr,"until finish use %.6lf seconds\n",double(clock()-st)/CLOCKS_PER_SEC);
    return 0;
}