#include <cstdio>

#include <algorithm>

#include <cstring>

#include <climits>

using namespace std;

const int N=1000010;

int T[N*4],C[N*4],n,M,m;

struct data{int v,x;}p[N];

long long ans;

bool cmp(data a,data b){return a.v<b.v;}

void add(int x,int y){

    T[x+=M]=y; C[x]=y;

    for(x/=2;x;x/=2){

        T[x]=max(T[x<<1],T[(x<<1)^1]);

        C[x]=min(C[x<<1],C[(x<<1)^1]);

    }

}

int query(int x,int y){

    int t=INT_MIN,c=INT_MAX;

    x+=M-1;y+=M+1;

    while(x^y^1>0){

        if(~x&1)t=max(T[x+1],t),c=min(C[x+1],c);

        if(y&1)t=max(T[y-1],t),c=min(C[y-1],c);

        x>>=1;y>>=1;

    }return t-c;

}

int main(){

    scanf("%d%d",&n,&m);

    for(M=1;M<n;M<<=1);

    for(int i=0;i<=M+n;i++)C[i]=INT_MAX,T[i]=INT_MIN;

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

        int x; scanf("%d",&x);

        add(i,x);

    }

    while(m--){

        int l,r; scanf("%d%d",&l,&r);

        printf("%d\n",query(l,r));

    }return 0;

}