#include<iostream>#include<cstdio>#include<cstring>using namespace std;int n, q;const int maxn = 111111;int dp[maxn][20];int dp1[maxn][20];int a[maxn];void gao(){    for (int i = 0; i < n; i++)        dp[i][0] = a[i];    for (int j = 1; (1 << j) <= n; j++){        for (int i = 0; i + (1 << j) - 1 < n; i++){            dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j-1))][j - 1]);        }    }}int ask(int l, int r){    int k = 0;    while ((1 << (k + 1)) <= r - l + 1) k++;    return min(dp[l][k], dp[r-(1<<k)+1][k]);}void gao1(){    memset(dp1,0,sizeof(dp1));    for (int i = 0; i < n; i++)        dp1[i][0] = a[i];    for (int j = 1; (1 << j) <= n; j++){        for (int i = 0; i + (1 << j) - 1 < n; i++){            dp1[i][j] = max(dp1[i][j - 1], dp1[i + (1 << (j-1))][j - 1]);        }    }}int ask1(int l, int r){    int k = 0;    while ((1 << (k + 1)) <= r - l + 1) k++;    return max(dp1[l][k], dp1[r + 1 - (1 << k)][k]);}int main(){    int l, r;    while (cin >> n >> q){        for (int i = 0; i < n; i++)            scanf("%d",&a[i]);        gao(); gao1();        for (int i = 0; i < q; i++){            scanf("%d%d",&l,&r);            l--;r--;            printf("%d\n",ask1(l,r)- ask(l,r));        }    }    return 0;}