#include<iostream>

#include<cstdio>

#include<algorithm>

#include<ctype.h>

#include<cstring>

using namespace std;

const int maxn=50005;

inline int read()

{

    int x=0,w=0;char c=getchar();

    while(!isdigit(c))w|=c=='-',c=getchar();

    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();

    return w?-x:x;

}

struct SegmentTree

{

    struct Node{

        int l,r;

        int mx,mn;

        int tagmx,tagmn;

    }e[4*maxn];

    #define ls (ro<<1)

    #define rs (ro<<1|1)

    #define INF 0x3f3f3f3f

    int maxx,minn;

    int n,m;

    void build(int ro,int l,int r)

    {

        e[ro].l=l,e[ro].r=r;

        e[ro].mn=INF,e[ro].mx=-INF;

        if(l==r)return ;

        int mid=(l+r)>>1;

        build(ls,l,mid);

        build(rs,mid+1,r);

    }

    void insert(int ro,int i,int k)

    {

        if(e[ro].l==e[ro].r){

            e[ro].mx=e[ro].mn=k;return;

        }

        e[ro].mn=min(e[ro].mn,k);

        e[ro].mx=max(e[ro].mx,k);

        int mid=(e[ro].l+e[ro].r)>>1;

        if(i<=mid)insert(ls,i,k);

        else insert(rs,i,k);

    }

    void query(int ro,int l,int r)

    {

        if(e[ro].mn>=minn and e[ro].mx<=maxx)return ;

        if(e[ro].l==l and e[ro].r==r){

            minn=min(minn,e[ro].mn);

            maxx=max(maxx,e[ro].mx);

            return;

        }

        int mid=(e[ro].l+e[ro].r)>>1;

        if(r<=mid)query(ls,l,r);

        else if(l>mid)query(rs,l,r);

        else {query(ls,l,mid);query(rs,mid+1,r);}

    }

    inline void getans()

    {

        n=read();m=read();

        build(1,1,n);

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

            insert(1,i,read());

        for(int i=1;i<=m;i++)

        {

            maxx=-INF,minn=INF;

            int l=read(),r=read();

            query(1,l,r);

            printf("%d\n",maxx-minn);

        }

        return ;

    }

    #undef ls

    #undef rs

    #undef INF

}st;

int main()

{

    st.getans();

    return 0;

}