一道（个人感觉）比较困难的数据结构题 qwq。但都距离 2009 过了十几年了现在应该挺板的。
这题怎么和我年龄差不多啊。
观察到本题最后面有说 数据为全部纯随机生成。这启发我们充分发扬人类智慧。
然而本题有 双倍经验 以及 三倍经验，为了水三道黑题，你决定采用和数据随机无关的做法。
即使现在 RMJ 炸了。

观察到没有强制在线，而且没有修改操作，考虑离线下来计算答案。
对于一个右端点 $r$，我们统计 $ans_l$ 表示 $[l,r]$ 中的最小绝对值差，则对于一个询问 $l,r$，相当于求扫到 $r$ 时候的 $[l,r]$ 后缀答案。
我们继续发扬人类智慧，考虑会对答案产生贡献的点对 $(i,j)$ 有什么特点。
先把绝对值拆掉，改成对于 $i \lt j, a_i \lt a_j$ 和 $i \lt j, a_i \gt a_j$ 分别统计答案。
以 $i \lt j, a_i \lt a_j$ 为例，产生贡献的第一个 $j$ 应该是满足 $a_j \in (a_i,+\infty)$ 的数中满足 $j \in (i,n]$ 的最小 $j$。
设第二个会产生贡献的点是 $k$，那么 $k$ 应该是满足 $a_k \in (a_i,\lfloor \frac{a_i+a_j}{2} \rfloor]$ 的数中满足 $k \in (j,n]$ 的最小 $k$。
因为如果 $a_k \gt \lfloor \frac{a_i+a_j}{2} \rfloor$，那么它距离 $a_j$ 更近就不会对 $i$ 产生贡献了。

观察到每次值域减小一半，因此总点数是 $O(\log V)$ 级别的。
那么由于扫描右端点 $r$，所以要反过来做，每次查询最大值。查询一段值域的下标最大值显然可以主席树，然后维护后缀答案可以采用树状数组。

注意本题要求两数不能相等，而经验题允许相等。
以及数据范围不同。

#include <bits/stdc++.h>
#define PII pair<int, int>
using namespace std;
const int N = 1e5 + 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 (int i = 1; i <= tot; i++) tr[i].ls = tr[i].rs = tr[i].Max = 0;
        tot = 0;
    }

    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);
    }

    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];
    void init() {
        for (int i = 0; i <= n; i++) tr[i] = INF;
    }
    void add(int x, int d) {
        for (; x ; x -= x & -x) tr[x] = min(tr[x], d);
    }
    int query(int x) {
        int res = INF;
        for (; x <= n; x += x & -x) res = min(res, tr[x]);
        return res;
    }
} bit;

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

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (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 (int i = 1; i <= n; i++) a[i] = -a[i] + INF;    //加上偏移量。
    solve();
    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}

至于三倍经验，首先注意 $m \leq 10^6$，然后还要卡常，需要把 vector 改成排序加指针。
隔壁学长提供的“超级快读快写”代码：

char buf[1 << 20], *p1 = buf, *p2 = buf, ouf[1 << 23], *p3 = ouf;

char input()
{
    if (p1 == p2)
        p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin);
    return *(p1++);
}

void read(int &x)
{
    static char ch = input();
    x = 0;
    while (!isdigit(ch))
        ch = input();
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = input();
}

void write(int x)
{
    if (x > 9)
        write(x / 10);
    *(p3++) = x % 10 ^ 48;
}

#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;
char buf[1 << 20], *p1 = buf, *p2 = buf, ouf[1 << 23], *p3 = ouf;

char input()
{
    if (p1 == p2)
        p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin);
    return *(p1++);
}

void read(int &x)
{
    static char ch = input();
    x = 0;
    while (!isdigit(ch))
        ch = input();
    while (isdigit(ch))
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = input();
}

void write(int x)
{
    if (x > 9)
        write(x / 10);
    *(p3++) = x % 10 ^ 48;
}

const int N = 3e5 + 15, M = 1e6 + 15, INF = 0x3f3f3f3f;
int n, m, a[N];
struct node {
    int l, r, id;
} q[M];
bool cmp(node a, node b) {
    return a.r < b.r;
}
int ans[M];

struct Segment_Tree {
    struct Tree {
        int ls, rs;
        int Max;
    } tr[N << 2];
    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 + 1; 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, p = 1;
    for (register int i = 1; i <= n; i++) {
        int now = tr.query(root, 0, n, a[i], n);
        while (now > 0) {
            bit.add(now, a[now] - a[i]);
            if (a[i] == a[now]) break;
            now = tr.query(root, 0, n, a[i], (a[i] + a[now]) / 2);
        }
        tr.change(root, 0, n, a[i], i);
        while (p <= m && q[p].r == i) ans[q[p].id] = min(ans[q[p].id], bit.query(q[p].l)), p++;
        // for (register PII u : l[i]) ans[u.second] = min(ans[u.second], bit.query(u.first));
    }
}

int main() {
    read(n), read(m);
    for (register int i = 1; i <= n; i++) read(a[i]);
    for (register int i = 1, x, y; i <= m; i++) {
        read(q[i].l), read(q[i].r), q[i].id = i;
        ans[i] = 0x3f3f3f3f;
    }
    sort(q + 1, q + 1 + m, cmp);
    solve();
    for (register int i = 1; i <= n; i++) a[i] = -a[i] + n;    //加上偏移量。
    solve();
    // for (int i = 1; i <= m; i++) cout << ans[i] << endl;
    for (int i = 1; i <= m; i++)
        write(ans[i]), *(p3++) = '\n';
    fwrite(ouf, 1, p3 - ouf, stdout);
    return 0;
}