思路：$ST$ 表

但是好像就第一个点过了……

好球没打 $ST$ 表了 qwq 都蒻成这样了

#include<bits/stdc++.h>
#define int long long
// #pragma GCC target("avx")
// #pragma GCC optimize(3,"Ofast","inline")
namespace FastIO {
	inline int read () {
		int x = 0, f = 1;
		char ch = getchar ();
		while (ch < '0' || ch > '9') {
			if (ch == '-')
				f = -1;
			ch = getchar ();
		}
		while (ch >= '0' && ch <= '9') {
			x = (x << 1) + (x << 3) + (ch ^ 48);
			ch = getchar ();
		}
		return x * f;
	}

	template<typename T> inline void read (T &x) {
		x = read ();
		return;
	}

	template<typename T,typename... Args> inline void read (T &x,Args &...x_) {
		read (x);
		read (x_...);
		return;
	}
}

namespace Constants {
	const int INF = 1e18;
	const int DIR[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
	const double EPS = 1e-7;
	const double PI = 3.14159265358979323;
}

using namespace std;
using namespace FastIO;
using namespace Constants;

inline void CLOSE () {
	ios::sync_with_stdio (false);
	cin.tie (nullptr);
	cout.tie (nullptr);
	return;
}

const int N = 5e4 + 10;

int n, m;
int a[N], Log[N];
int dp[N][20][2];

void Init_st () {
	Log[0] = -1;
	for (int i = 1; i <= n; i++) {
		Log[i] = Log[i >> 1] + 1;
		dp[i][0][0] = a[i];
		dp[i][0][1] = a[i];
	}

	for (int j = 1; j <= 16; j++) {
		for (int i = 1; i + (1 << j) - 1 <= n; i++) {
			dp[i][j][0] = min (dp[i][j - 1][0], dp[i + (1 << j) - 1][j - 1][0]);
			dp[i][j][1] = max (dp[i][j - 1][1], dp[i + (1 << j) - 1][j - 1][1]);
		}
	}
	return;
}

int Ask_min (int l, int r) {
	int k = Log[r - l + 1];
	return min (dp[l][k][0], dp[r - (1 << k) + 1][k][0]);
}

int Ask_max (int l, int r) {
	int k = Log[r - l + 1];
	return max (dp[l][k][1], dp[r - (1 << k) + 1][k][1]);
}

signed main() {
	CLOSE ();
	read (n, m);
	for (int i = 1; i <= n; i++) {
		read (a[i]);
	}
	Init_st ();

	while (m--) {
		int l = read (), r = read ();
		cout << Ask_max (l, r) - Ask_min (l, r) << endl;
	}
	return 0;
}