//

#include <iostream>

#include <stdio.h>

#include <vector>

#include <algorithm>

#include <string>

#include <stack>

#include <math.h>

#include <vector>

#include <string.h>

using namespace std;

typedef __int64 ll;

const int inf = (int)1E9+;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//*******************************

struct ss

{

    int l,r,mn,ma;

}tr[];

int n,q,a[],nn,mm;

void build(int k,int s,int t)

{

    tr[k].l=s;

    tr[k].r=t;

    if(s==t){

        tr[k].mn=tr[k].ma=a[s];

        return ;

    }

    int mid=(s+t)>>;

    build(k<<,s,mid);

    build(k<<|,mid+,t);

    tr[k].ma=max(tr[k<<].ma,tr[k<<|].ma);

    tr[k].mn=min(tr[k<<].mn,tr[k<<|].mn);

}

void ask(int k,int s,int t)

{

    if(tr[k].ma<=nn&&tr[k].mn>=mm)return;

    if(s==tr[k].l&&t==tr[k].r)

    {

        nn=max(tr[k].ma,nn);

        mm=min(tr[k].mn,mm);

        return;

    }

    int mid=(tr[k].l+tr[k].r)>>;

    if(t<=mid) ask(k<<,s,t);

    else if(s>mid) ask(k<<|,s,t);

    else {

       ask(k<<,s,mid);

       ask(k<<|,mid+,t);

    }

}

int main()

{

    while(scanf("%d%d",&n,&q)!=EOF)

    {

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

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

        }build(,,n);int x,y;

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

                nn=-inf;

               mm=inf;

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

            ask(,x,y);

            printf("%d\n",nn-mm);

        }

    }

    return ;

}