#include <iostream>#include<cstdio>#include<cstring>using namespace std;const int MAX = 200000+5;int N,Q,a[MAX];int ansMin,ansMax;struct Tree{    int l,r,mins,maxs;}tree[4*MAX];///建立线段树,cnt为节点角标,a[l]-a[r]建树void build(int cnt,int l,int r){    tree[cnt].l = l,tree[cnt].r = r;    if(l==r)    {        tree[cnt].mins = tree[cnt].maxs = a[l];        return;    }    int mid = (l + r)/2;    build(2*cnt,l,mid);    build(2*cnt+1,mid+1,r);    ///回溯建立父节点    tree[cnt].mins = min(tree[2*cnt].mins,tree[2*cnt+1].mins);    tree[cnt].maxs = max(tree[2*cnt].maxs,tree[2*cnt+1].maxs);}///查询区间l-r的最大值和最小值void query(int cnt,int l,int r){    if(tree[cnt].mins>=ansMin&&tree[cnt].maxs<=ansMax)        return;    if(tree[cnt].l==l&&tree[cnt].r==r)    {        ansMax = max(tree[cnt].maxs,ansMax), ansMin = min(tree[cnt].mins,ansMin);        return;    }    ///分三种情况讨论    int mid = (tree[cnt].l+tree[cnt].r)/2;    if(r<=mid)///在mid右端        query(2*cnt,l,r);    else if(l>mid)///在mid左端        query(2*cnt+1,l,r);    else///两端    {        query(2*cnt,l,mid);        query(2*cnt+1,mid+1,r);    }}int main(){    //freopen("in.txt","r",stdin);    while(scanf("%d%d",&N,&Q)!=EOF)    {        memset(tree,0,sizeof(tree));        for(int i=1;i<=N;i++)            scanf("%d",&a[i]);        int left,right;        build(1,1,N);        for(int i=1;i<=Q;i++)        {            ansMin = 0x3f3f3f3f, ansMax = -1;            scanf("%d%d",&left,&right);            query(1,left,right);            printf("%d\n",ansMax-ansMin);        }    }    return 0;}