#include <bits/stdc++.h>
#define int long long 
#define MAXN 50010
int h[MAXN],stmax[MAXN][18],stmin[MAXN][18],log_2[MAXN];
int n,q;

void init(){
    for(int i=1;1<=n;i++){
        stmax[i][0] = h[i];
        stmin[i][0] = h[i];
    }
    for(int j = 1;(1<<j)<=n;j++){
        for(int i=1;i<=n-(1<<j)+1;i++){
            stmax[i][j] = std::max(stmax[i][j-1],stmax[i+(1<<j-1)][j-1]);
            stmin[i][j] = std::min(stmin[i][j-1],stmin[i+(1<<j-1)][j-1]);
        }
    }
}

int query_max(int l,int r){
    int k = log_2[r-l+1];
    return std::max(stmax[l][k],stmax[r-(1<<k)+1][k]);
}

int query_min(int l,int r){
    int k = log_2[r-l+1];
    return std::min(stmin[l][k],stmin[r-(1<<k)+1][k]);
}

signed main(){
    std::cin.tie(0)->std::ios::sync_with_stdio(false);
    std::cin>>n>>q;
    for(int i=1;i<=n;i++){
        std::cin>>h[i];
    }
    for(int i=2;i<=n;i++){
        log_2[i]=log_2[i>>1]+1;
    }
    init();
    while(q--){
        int a,b;
        std::cin>>a>>b;
        std::cout<<query_max(a,b)-query_min(a,b)<<std::endl;
    }
    return 0;
}