//2025/4/10 19:32 - 19:39
#include<bits/stdc++.h>
using namespace std;
const int N = 50010;
int dp_min[N][30], dp_max[N][30], h[N];
int n, m;
int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        cin >> h[i];
        dp_min[i][0] = dp_max[i][0] = h[i];
    }

    for(int j=1;(1<<j)<=n;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            dp_min[i][j] = min(dp_min[i][j-1], dp_min[i+(1<<(j-1))][j-1]);
            dp_max[i][j] = max(dp_max[i][j-1], dp_max[i+(1<<(j-1))][j-1]);
        }
    }

    while(m--)
    {
        int l, r;
        cin >> l >> r;
        int mid = log(r-l+1)/log(2);
        int max_num = max(dp_max[l][mid], dp_max[r-(1<<mid)+1][mid]);
        int min_num = min(dp_min[l][mid], dp_min[r-(1<<mid)+1][mid]);
        cout << max_num - min_num << endl;
    }
    return 0;
}