#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define lowbit(x) (x & (-x))

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 50000 + 10;

const int MAXT = 10000 + 10;

using namespace std;

int a[MAXN];

int minv[MAXN << 2], maxv[MAXN << 2];

int _min, _max;

void build(int id, int L, int R){

    if(L == R){

        minv[id] = maxv[id] = a[L];

    }

    else{

        int mid = L + (R - L) / 2;

        build(id << 1, L, mid);

        build(id << 1 | 1, mid + 1, R);

        minv[id] = min(minv[id << 1], minv[id << 1 | 1]);

        maxv[id] = max(maxv[id << 1], maxv[id << 1 | 1]);

    }

}

void query(int l, int r, int id, int L, int R){

    if(l <= L && R <= r){

        _max = max(_max, maxv[id]);

        _min = min(_min, minv[id]);

        return;

    }

    int mid = L + (R - L) / 2;

    if(l <= mid){

        query(l, r, id << 1, L, mid);

    }

    if(r > mid){

        query(l, r, id << 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);

    while(Q--){

        int A, B;

        scanf("%d%d", &A, &B);

        _min = INT_INF;

        _max = 0;

        query(A, B, 1, 1, N);

        printf("%d\n", _max - _min);

    }

    return 0;

}

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define lowbit(x) (x & (-x))

const double eps = 1e-8;

inline int dcmp(double a, double b){

    if(fabs(a - b) < eps) return 0;

    return a > b ? 1 : -1;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};

const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};

const int MOD = 1e9 + 7;

const double pi = acos(-1.0);

const int MAXN = 50000 + 10;

const int MAXT = 10000 + 10;

using namespace std;

int a[MAXN];

int N, Q;

int minv[MAXN][20];

int maxv[MAXN][20];

void RMQ_init(){

    for(int i = 1; i <= N; ++i){

        minv[i][0] = maxv[i][0] = a[i];

    }

    for(int j = 1; (1 << j) <= N; ++j){

        for(int i = 1; (i + (1 << j) - 1) <= N; ++i){

            minv[i][j] = min(minv[i][j - 1], minv[i + (1 << (j - 1))][j - 1]);

            maxv[i][j] = max(maxv[i][j - 1], maxv[i + (1 << (j - 1))][j - 1]);

        }

    }

}

int RMQ(int L, int R){

    int k = 0;

    while((1 << (k + 1)) <= (R - L + 1)) ++k;

    return max(maxv[L][k], maxv[R - (1 << k) + 1][k]) - min(minv[L][k], minv[R - (1 << k) + 1][k]);

}

int main(){

    scanf("%d%d", &N, &Q);

    for(int i = 1; i <= N; ++i){

        scanf("%d", &a[i]);

    }

    RMQ_init();

    while(Q--){

        int A, B;

        scanf("%d%d", &A, &B);

        printf("%d\n", RMQ(A, B));

    }

    return 0;

}