#include <cstdio>#include <algorithm>using namespace std;const int MAX_N = 50000 + 10;const int INF = 0x3f3f3f3f;struct Node {    int l, r;    int minv, maxv;} t[MAX_N << 2];int a[MAX_N], minv, maxv;void build(int o, int l, int r) {    t[o].l = l; t[o].r = r;    if (l == r) {        t[o].minv = t[o].maxv = a[l];        return;    }    int mid = (l + r) >> 1;    build(o << 1, l, mid);    build(o << 1 | 1, mid + 1, r);    t[o].maxv = max(t[o << 1].maxv, t[o << 1 | 1].maxv);    t[o].minv = min(t[o << 1].minv, t[o << 1 | 1].minv);}void query(int o, int l, int r) {    if (t[o].maxv <= maxv && t[o].minv >= minv) return;    if (t[o].l == l && t[o].r == r) {        maxv = max(maxv, t[o].maxv);        minv = min(minv, t[o].minv);        return;    }    int mid = (t[o].l + t[o].r) >> 1;    if (r <= mid) query(o << 1, l, r);    else if (l > mid) query(o << 1 | 1, l, r);    else {        query(o << 1, l, mid);        query(o << 1 | 1, mid + 1, r);    }}int main() {    int N, Q;    scanf("%d%d", &N, &Q);    for (int i = 1; i <= N; i++)         scanf("%d", &a[i]);    build(1, 1, N);    for (int i = 0; i < Q; i++) {        int l, r;        scanf("%d%d", &l, &r);        minv = INF; maxv = -INF;        query(1, l, r);        printf("%d\n", maxv - minv);    }    return 0;}