rt，只过了样例

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;

int n, m;
int a[N], b[N];
vector<pair<int, int>> q[N];
vector<pair<int, int>> useful[N];
int ans[N];
int c[N];
vector<int> nums;
struct SegT {
	int lc, rc;
	int val;
	#define lc(x) tr[x].lc
	#define rc(x) tr[x].rc
	#define val(x) tr[x].val
} tr[N << 5];
int idx, rt[N];

void build (int &x, int l, int r) {
	x = ++ idx;
	val(x) = n + 1;
	if (l == r) {
		return;
	}
	int mid = (l + r) / 2;
	build(lc(x), l, mid), build(rc(x), mid + 1, r);
}

void update(int &x, int y, int l, int r, int p, int v) {
	x = ++ idx;
	tr[x] = tr[y];
	val(x) = v;
	if (l == r) {
		return;
	}
	int mid = (l + r) / 2;
	if (p <= mid) {
		update(lc(x), lc(y), l, mid, p, v);
	} else {
		update(rc(x), rc(y), mid + 1, r, p, v);
	}
}

int query(int x, int l, int r, int ql, int qr) {
	if (!x || ql > qr) {
		return n + 1;
	}
	if (ql <= l && r <= qr) {
		return val(x);
	}
	int mid = (l + r) / 2, res = n + 1;
	if (ql <= mid) {
		res = min(res, query(lc(x), l, mid, ql, qr));
	}
	if (qr > mid) {
		res = min(res, query(rc(x), mid + 1, r, ql, qr));
	}
	return res;
}

void solve() {
	nums.clear();
	idx = 0;
	build(rt[n + 1], 1, n);
	for (int i = 1; i <= n; i ++) {
		nums.push_back(a[i]);
	}
	sort(nums.begin(), nums.end());
	nums.erase(unique(nums.begin(), nums.end()), nums.end());
	for (int i = 1; i <= n; i ++) {
		b[i] = lower_bound(nums.begin(), nums.end(), a[i]) - nums.begin() + 1;
	}
	for (int i = n; i >= 1; i --) {
		update(rt[i], rt[i + 1], 1, n, b[i], i);
	}
	for (int i = 1; i <= n; i ++) {
		int x;
		x = query(rt[i + 1], 1, n, b[i] + 1, n);
		while (x != n + 1) {
			useful[x].emplace_back(i, a[x] - a[i]);
			int p = (a[i] + a[x]) / 2;
			p = lower_bound(nums.begin(), nums.end(), p) - nums.begin();
			x = query(x + 1, 1, n, b[i] + 1, p);
		}
	}
}

void add(int x, int v) {
	for (; x; x -= x & -x) {
		c[x] = min(c[x], v);
	}
}

int ask(int x) {
	int res = 1e9;
	for (; x <= n; x += x & -x) {
		res = min(res, c[x]);
	}
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	solve();
	for (int i = 1; i <= n; i ++) {
		a[i] = -a[i];
	}
	solve();
	for (int i = 1; i <= n; i ++) {
		a[i] = -a[i];
	}

	for (int i = 1; i <= m; i ++) {
		int l, r;
		cin >> l >> r;
		q[r].emplace_back(l, i);
	}
	
	// l <= l' <= r' <= r
	
	for (int i = 1; i <= n; i ++) {
		c[i] = 1e9;
	}

	for (int r = 1; r <= n; r ++) {
		for (auto t : useful[r]) {
			int l = t.first, v = t.second;
			add(l, v);
		}
		for (auto t : q[r]) {
			int l = t.first, id = t.second;
			ans[id] = ask(l);
		}
	}

	for (int i = 1; i <= m; i ++) {
		cout << ans[i] << "\n";
	}

	return 0;
}