#include <bits/stdc++.h>

using namespace std;

const int maxN = 1e6 + 5;
const int maxQ = 1e6 + 5;

random_device seed;
mt19937 rd{seed()};

int n, qu, a[maxN], bl[maxN], L[maxN], R[maxN], T, block, ans[maxQ];

struct que {
    int l, r, id;

    bool operator < (const que &x) const {
        return bl[l] == bl[x.l] ? r < x.r : bl[l] < bl[x.l];
    }
} q[maxQ];

struct Treap {
    int rt, tot;
    int val[maxN], ch[maxN][2], pro[maxN], sz[maxN];

    int newNode(int x) {
        val[++tot] = x;
        pro[tot] = (int) rd();
        sz[tot] = 1;
        return tot;
    }

    void maintain(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1; }

    void splitV(int x, int k, int &l, int &r) {
        if (!x) return l = r = 0, void();
        if (val[x] <= k) splitV(ch[x][1], k, ch[l = x][1], r);
        else splitV(ch[x][0], k, l, ch[r = x][0]);
        maintain(x);
    }

    void splitR(int x, int rk, int &l, int &r) {
        if (!x) return l = r = 0, void();
        int ls = sz[ch[x][0]] + 1;
        if (rk >= ls) splitR(ch[x][1], rk - ls, ch[l = x][1], r);
        else splitR(ch[x][0], rk, l, ch[r = x][0]);
        maintain(x);
    }

    int merge(int u, int v) {
        if (!u || !v) return u | v;
        if (pro[u] < pro[v]) return ch[u][1] = merge(ch[u][1], v), maintain(u), u;
        else return ch[v][0] = merge(u, ch[v][0]), maintain(v), v;
    }

    void ins(int x) {
        int l, r;
        splitV(rt, x, l, r);
        rt = merge(merge(l, newNode(x)), r);
    }

    void del(int x) {
        int l, mid, r;
        splitV(rt, x, l, r);
        splitV(l, x - 1, l, mid);
        mid = merge(ch[mid][0], ch[mid][1]);
        rt = merge(merge(l, mid), r);
    }

    int kth(int &root, int rk) {
        if (rk > sz[root]) return -1;
        int l, mid, r;
        splitR(root, rk, l, r);
        splitR(l, rk - 1, l, mid);
        int res = val[mid];
        root = merge(merge(l, mid), r);
        return res;
    }

    int pre(int k) {
        int l, r;
        splitV(rt, k - 1, l, r);
        int res = -1;
        if (l != 0) res = kth(l, sz[l]);
        rt = merge(l, r);
        return res;
    }

    int nxt(int k) {
        int l, r;
        splitV(rt, k, l, r);
        int res = -1;
        if (r != 0) res = kth(r, 1);
        rt = merge(l, r);
        return res;
    }
} tr, tmp;

void add(int x, int &fz) {
    tr.ins(a[x]);
    int p = tr.pre(a[x]), t = tr.nxt(a[x]);
    if (p != -1) fz = min(fz, a[x] - p);
    if (t != -1) fz = min(fz, t - a[x]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n >> qu;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= qu; ++i) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    block = (int) sqrt(n);
    ++block;
    T = n / block;
    for (int i = 1; i <= T; ++i) {
        L[i] = R[i - 1] + 1;
        R[i] = i * block;
    }
    if (R[T] < n) {
        ++T;
        L[T] = R[T - 1] + 1;
        R[T] = n;
    }
    for (int i = 1; i <= T; ++i) {
        for (int j = L[i]; j <= R[i]; ++j) bl[j] = i;
    }
    sort(q + 1, q + 1 + qu);
//    for (int i = 1; i <= qu; ++i) {
//        cout << q[i].l << ' ' << q[i].r << '\n';
//    }
//    for (int i = 1; i <= T; ++i) {
//        cout << L[i] << ' ' << R[i] << '\n';
//    }
    int l = 1, r = 0, last = 0;
    int fz = 1145141919;
    for (int i = 1; i <= qu; ++i) {
        int x = q[i].l, y = q[i].r;
        if (bl[x] == bl[y]) {
//            cout << x << ' ' << y << '\n';
            int minn = 1145141919;
            for (int j = x; j <= y; ++j) tmp.ins(a[j]);
            for (int j = x; j <= y; ++j) {
                int p = tmp.pre(a[j]), t = tmp.nxt(a[j]);
                if (p != -1) minn = min(a[j] - p, minn);
                if (t != -1) minn = min(t - a[j], minn);
            }
            for (int j = x; j <= y; ++j) tmp.del(a[j]);
            ans[q[i].id] = minn;
        } else {
            if (last ^ bl[x]) {
                while (r > R[bl[x]]) tr.del(a[r--]);
                while (r < R[bl[x]]) tr.ins(a[++r]);
                while (l <= R[bl[x]]) tr.del(a[l++]);
//                cout << l << ' ' << r << '\n';
                fz = 1145141919, last = bl[x];
            }
            while (r < y) add(++r, fz);
//            cout << fz << '\n';
            int fm = fz;
            int l_ = l;
            while (l_ > x) add(--l_, fm);
            ans[q[i].id] = fm;
            while (l_ < l) tr.del(a[l_++]);
        }
    }
    for (int i = 1; i <= qu; ++i) cout << ans[i] << '\n';

    return 0;
}