#include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 #define N 50010

 #define INF 0x3f3f3f3f

 int dpmin[N][], dpmax[N][], n;

 void Init() {

     memset(dpmin, INF, sizeof(dpmin));

     for(int i = ; i <= n; i++) { scanf("%d", &dpmin[i][]); dpmax[i][] = dpmin[i][]; }

     int limit = (int)(log(n) / log());

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

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

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

 }

 int Query(int l, int r) {

     int k = (int)(log(r - l + ) / log());

     return max(dpmax[l][k], dpmax[r-(<<k)+][k]) - min(dpmin[l][k], dpmin[r-(<<k)+][k]);

 }

 int main() {

     int q;

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

         Init();

         while(q--) {

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

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

         }

     }

     return ;

 }