其余两倍经验都过了，但这题不知道是被卡常还是死循环，调不出来了 qwq。

#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
#define PII pair<int, int>
using namespace std;
const int N = 3e5 + 15, INF = 0x3f3f3f3f;
int n, m, a[N];
vector< PII > l[N];   //对于右端点记录左端点询问
int ans[N];

struct Segment_Tree {
    struct Tree {
        int ls, rs;
        int Max;
    } tr[N << 5];
    int tot = 0;
    
    void init() {
        for (register int i = 1; i <= tot; i++) tr[i].ls = tr[i].rs = tr[i].Max = 0;
        tot = 0;
    }
    
    inline void change(int &u, int l, int r, int x, int d) {
        if (!u) u = ++tot;
        tr[u].Max = max(tr[u].Max, d);
        if (l == r) return;
        int mid = l + r >> 1;
        if (x <= mid) change(tr[u].ls, l, mid, x, d);
        else change(tr[u].rs, mid + 1, r, x, d);
    }
    
    inline int query(int u, int l, int r, int ql, int qr) {
        if (r < ql || l > qr || !u) return 0;
        if (l >= ql && r <= qr) return tr[u].Max;
        int mid = l + r >> 1, res = 0;
        if (ql <= mid) res = max(res, query(tr[u].ls, l, mid, ql, qr));
        if (qr > mid) res = max(res, query(tr[u].rs, mid + 1, r, ql, qr));
        return res;
    }
} tr;

struct BIT {
    int tr[N];
    inline void init() {
        for (register int i = 0; i <= n; i++) tr[i] = INF;
    }
    inline void add(int x, int d) {
        for (; x ; x -= x & -x) tr[x] = min(tr[x], d);
    }
    inline int query(int x) {
        int res = INF;
        for (; x <= n; x += x & -x) res = min(res, tr[x]);
        return res;
    }
} bit;

inline void solve() {
    tr.init(), bit.init();
    int root = 0;
    for (register int i = 1; i <= n; i++) {
        int now = tr.query(root, 0, INF, a[i], INF);
        while (now > 0) {
            bit.add(now, a[now] - a[i]);
            if (a[i] == a[now]) break;
            now = tr.query(root, 0, INF, a[i], (a[i] + a[now]) / 2);
        }
        tr.change(root, 0, INF, a[i], i);
        for (register PII u : l[i]) ans[u.second] = min(ans[u.second], bit.query(u.first));
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (register int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (register int i = 1, x, y; i <= m; i++) {
        scanf("%d%d", &x, &y);
        l[y].push_back(make_pair(x, i));
        ans[i] = 0x3f3f3f3f;
    }
    solve();
    for (register int i = 1; i <= n; i++) a[i] = -a[i] + INF;    //加上偏移量。
    solve();
    for (register int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}