#include<iostream>

#include<cmath>

#include<cstdio>

#define N 50005

using namespace std;

int maxx[N][],minn[N][],a[N];

int ST(int n)

{

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

    {

        maxx[i][]=a[i];

        minn[i][]=a[i];

    }

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

    {

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

        {

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

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

        }

    }

}

int main()

{

    int n,q,lf,rg,mx,mn;

    cin>>n>>q;

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

    {

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

    }

    ST(n);

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

    {

        scanf("%d %d",&lf,&rg);

        int k=log2(rg-lf+);

        mx=max(maxx[lf][k],maxx[rg-(<<k)+][k]);

        mn=min(minn[lf][k],minn[rg-(<<k)+][k]);

        cout<<mx-mn<<endl;

    }

}