#include <bits/stdc++.h> using namespace std; const int nmax = 1e5 + 1; const int oo = 1e9 + 1; int h[nmax]; int n, q; int itmax[4 * nmax]; int itmin[4 * nmax]; void buildMAX(int i, int l, int r) { if (r == l) { itmax[i] = h[l]; return; } int il = i * 2, mid = (l + r) / 2; buildMAX(il, l, mid); buildMAX(il + 1, mid + 1, r); itmax[i] = max(itmax[il], itmax[il + 1]); } void buildMIN(int i, int l, int r) { if (r == l) { itmin[i] = h[l]; return; } int il = i * 2, mid = (l + r) / 2; buildMIN(il, l, mid); buildMIN(il + 1, mid + 1, r); itmin[i] = min(itmin[il], itmin[il + 1]); } int querymax(int i, int l, int r, int u, int v) { if (r < u || v < l) return -oo; if (r <= v && l >= u) { return itmax[i]; } int il = 2 * i, mid = (l + r) / 2; return max(querymax(il, l, mid, u, v), querymax(il + 1, mid + 1, r, u, v)); } int querymin(int i, int l, int r, int u, int v) { if (r < u || v < l) return oo; if (r <= v && l >= u) { return itmin[i]; } int il = 2 * i, mid = (l + r) / 2; return min(querymin(il, l, mid, u, v), querymin(il + 1, mid + 1, r, u, v)); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; for (int i = 1; i <= n; i++) cin >> h[i]; buildMAX(1, 1, n); buildMIN(1, 1, n); while (q--) { int u, v; cin >> u >> v; cout << querymax(1, 1, n, u, v) - querymin(1, 1, n, u, v) << " "; } }