#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n, q;
    cin >> n >> q;
    vector<int> lg(n+1);
    vector<int> height(n);
    lg[1] = 0;
    for(int i = 2; i <= n; ++i){
        lg[i] = lg[i >> 1] + 1;
    }
    for(int i = 0; i < n; ++i){
        cin >> height[i];
    }
    vector<vector<int>> st_max(n, vector<int>(20));
    vector<vector<int>> st_min(n, vector<int>(20));

    // 初始化第 0 层（长度为 1 的区间）
    for(int i = 0; i < n; ++i) {
        st_max[i][0] = st_min[i][0] = height[i];
    }

    // 核心倍增预处理
    for(int j = 1; j <= lg[n]; ++j) { // 先枚举幂次
        for(int i = 0; i + (1 << j) <= n; ++i) { // 枚举起点，确保不越界
            // 长度为 2^j 的区间 = 两个长度为 2^(j-1) 的区间合并
            st_max[i][j] = max(st_max[i][j-1], st_max[i + (1 << (j-1))][j-1]);
            st_min[i][j] = min(st_min[i][j-1], st_min[i + (1 << (j-1))][j-1]);
        }
    }

    for(int i = 0; i < q; ++i){
        int a, b;
        cin >> a >> b;
        int len = b - a + 1;
        int k = lg[len];
        int res_max = max(st_max[a-1][k], st_max[b - (1 << k)][k]);
        int res_min = min(st_min[a-1][k], st_min[b - (1 << k)][k]);
        cout << res_max - res_min << endl;
    }
    return 0;
}













//dp困难方法
/*
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;
int main(){
    int n, q;
    cin >> n >> q;
    vector<int> height(n);
    vector<vector<int>> dp(n, vector<int>(n, INF));
    for(int i = 0; i < n; ++i){
        cin >> height[i];
        dp[i][i] = height[i];
    }
    //dp function: dp[i][j] = min(dp[i][k], dp[k][j])
    for(int i = 0; i < n; ++i){
        for(int j = 1; j < n; ++j){
            dp[i][j] = min(dp[i][j - 1], height[j]);
        }
    }
    for(int i = 0; i < q; ++i){
        int a, b;
        cin >> a >> b;
        cout << dp[a - 1][b - 1] << endl;
    }
    return 0;
}*/