#include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 const int MAXN = ;

 int min_dp[MAXN][],max_dp[MAXN][];

 int min_mm[MAXN],max_mm[MAXN];

 int b[MAXN];

 int N,Q;

 void min_initRMQ(int n,int b[])

 {

         min_mm[] = -;

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

         {

                 min_mm[i] = ( (i&(i-)) == ) ? min_mm[i-]+ : min_mm[i-];

                 min_dp[i][] = b[i];

         }

         for(int j=;j<=min_mm[n];j++)

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

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

 }

 int min_rmq(int x,int y)

 {

         int k = min_mm[y-x+];

         return min(min_dp[x][k],min_dp[y-(<<k)+][k]);

 }

 void max_initRMQ(int n,int b[])

 {

         max_mm[] = -;

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

         {

                 max_mm[i] = ( (i&(i-)) == ) ? max_mm[i-]+ : max_mm[i-];

                 max_dp[i][] = b[i];

         }

         for(int j=;j<=max_mm[n];j++)

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

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

 }

 int max_rmq(int x,int y)

 {

         int k = max_mm[y-x+];

         return max(max_dp[x][k],max_dp[y-(<<k)+][k]);

 }

 int main()

 {

         //freopen("input.in","r",stdin);

         while(~scanf("%d%d",&N,&Q))

         {

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

                 {

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

                 }

                 min_initRMQ(N,b);

                 max_initRMQ(N,b);

                 for(int i=,l,r;i<Q;i++)

                 {

                         scanf("%d%d",&l,&r);

                         printf("%d\n",max_rmq(l,r) - min_rmq(l,r) );

                         //printf("%d\n",max_rmq(l,r));

                 }

         }

 }