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

 题目：     Balanced Lineup(poj 3264)

 链接：     http://poj.org/problem?id=3264

 题意：     给个数列，查询一段区间的最大值与最小值的差

 算法：     RMQ

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

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<cmath>

 using namespace std;

 const int mx=;

 int dpmax[mx][];

 int dpmin[mx][];

 int a[mx];

 int n,q;

 void makermq()

 {

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

     {

         dpmax[i][]=a[i];

         dpmin[i][]=a[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-]);

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

         }

     }

 }

 int rmq(int u,int v)

 {

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

     return max(dpmax[u][k],dpmax[v-(<<k)+][k])-min(dpmin[u][k],dpmin[v-(<<k)+][k]);

 }

 int main()

 {

     scanf("%d%d",&n,&q);

     for (int i=;i<=n;i++) scanf("%d",&a[i]);

     makermq();

     while (q--)

     {

         int u,v;

         scanf("%d%d",&u,&v);

         printf("%d\n",rmq(u,v));

     }

 }