```cpp

#include<cstdio>

#include<iostream>
using namespace std;
int f[100005][50],g[100005][50],LOG2[100005],POW2[100005],p;
int query( int l, int r)
{
     p=LOG2[r-l+1];
     return (max(f[l][p],f[r-POW2[p]+1][p])-min(g[l][p],g[r-POW2[p]+1][p]));
}
int main()
{
     int n,q,a;
     scanf ( "%d%d" ,&n,&q);
     for ( int i=1;i<=n;i++)
     {
         
         scanf ( "%d" ,&a);
         f[i][0]=a;
         g[i][0]=a;
     }
     LOG2[1]=0;
     int i,j;
     for (i=2;i<=n;i++)
     {
         LOG2[i]=LOG2[i/2]+1;
     }
     POW2[0]=1;
     for (i=1;i<=LOG2[n];i++)
     {
         POW2[i]=POW2[i-1]*2;
     }
     for (j=1;j<=LOG2[n];j++)
     {
         for (i=1;(i+POW2[j-1])<=n;i++)
         {
             f[i][j]=max(f[i][j-1],f[i+POW2[j-1]][j-1]);
             g[i][j]=min(g[i][j-1],g[i+POW2[j-1]][j-1]);
         }
     }
     int x,y;
     for (i=1;i<=q;i++)
     {
         x,y;
         scanf ( "%d%d" ,&x,&y);
         printf ( "%d\n" ,query(x,y));
     }
     return 0;
}

```