#include <cstdio>

 #include <cstring>

 #include <iostream>

 using namespace std;

 const int N = ;

 #define INF 0x3f3f3f3f

 int maxn[N<<][] , minn[N<<][] , a[N];

 void build_dp(int n)

 {

     memset(maxn ,  , sizeof(maxn));

     memset(minn , 0x3f , sizeof(minn));

     for(int i= ; i<n ; i++) minn[i][]=maxn[i][]=a[i];

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

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

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

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

         }

     }

 }

 int get_index(int len)

 {

     int ans= , l=;

     while(l<len){

         l<<=;

         ans++;

     }

     return ans-;

 }

 int main()

 {

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

     int n , q , s , t;

     while(~scanf("%d%d" , &n , &q))

     {

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

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

         }

         build_dp(n);

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

             scanf("%d%d" , &s , &t);

             s-- , t--;

             int len=t-s+ , maxVal= , minVal=INF;

             if(s == t){

                 maxVal = maxn[s][];

                 minVal = minn[s][];

             }else{

                 int k=get_index(len);

                 maxVal = max(maxn[s][k] , maxn[t-(<<k)+][k]);

                 minVal = min(minn[s][k] , minn[t-(<<k)+][k]);

             }

             printf("%d\n" , maxVal-minVal);

         }

     }

     return ;

 }