#include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 using namespace std;

 const int maxn=;

 const int INF=0x3f3f3f3f;

 int n,m,t;

 const int MAXN = ;

 int dpMAX[MAXN][],dpMIN[MAXN][];

 int mm[MAXN];

 int cow[MAXN];

 //初始化RMQ, b数组下标从1开始，从0开始简单修改

 void makemaxRMQ(int n,int b[])

 {

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

       dpMAX[i][]=b[i];

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

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

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

 }

 int rmqMAX(int s,int v)

 {

     int k=(int)(log(v-s+1.0)/log(2.0));

     return max(dpMAX[s][k],dpMAX[v-(<<k)+][k]);

 }

 void makeminRMQ(int n,int b[])

 {

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

       dpMIN[i][]=b[i];

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

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

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

 }

 int rmqMIN(int s,int v)

 {

     int k=(int)(log(v-s+1.0)/log(2.0));

     return min(dpMIN[s][k],dpMIN[v-(<<k)+][k]);

 }

 int main()

 {

     int i,j,k;

     #ifndef ONLINE_JUDGE

     freopen("1.in","r",stdin);

     #endif

     int q;

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

     {

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

         {

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

         }

         makemaxRMQ(n,cow);

         makeminRMQ(n,cow);

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

         {

             int a,b;

             scanf("%d%d",&a,&b);

             printf("%d\n",rmqMAX(a,b)-rmqMIN(a,b));

         }

     }

     return ;

 }