#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

int n,q;

int a,b;

int maxsum,minsum;

int maxn[][];

int num[];

int minn[][];

void RMQ(int s)

{

    for(int j=;j<=;j++)

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

        if(i+(<<j)-<=n)

        {

            maxn[i][j]=max(maxn[i][j-],maxn[i+(<<(j-))][j-]);

            minn[i][j]=min(minn[i][j-],minn[i+(<<(j-))][j-]);

        }

    }

}

int main(){

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

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

    {

        scanf("%d",&num[i]);

        maxn[i][]=minn[i][]=num[i];

    }

    RMQ(n);

    for(int i=;i<=q;i++)

    {

        scanf("%d%d",&a,&b);

        int k=(int)(log(b-a+1.0)/log(2.0));

        maxsum=max(maxn[a][k],maxn[b-(<<k)+][k]);

        minsum=min(minn[a][k],minn[b-(<<k)+][k]);

        printf("%d\n",maxsum-minsum);

    }

}