#include <cstdio>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 const int INF = 0x3f3f3f3f;

 struct node

 {

     int L, R;

     int Min, Max;

     int Mid()

     {

         return (L + R) / ;

     }

 };

 node tree[maxn];

 int Min, Max;

 void build(int root, int l, int r)

 {

     tree[root].L = l;

     tree[root].R = r;

     tree[root].Min = INF;

     tree[root].Max = -INF;

     if (l == r)

         return ;

     build (*root+, l, tree[root].Mid());

     build (*root+, tree[root].Mid()+, r);

 }

 void insert (int root, int x, int s)

 {

     tree[root].Min = min (tree[root].Min, s);

     tree[root].Max = max (tree[root].Max, s);

     if (tree[root].L == tree[root].R)

         return ;

     if (x <= tree[root].Mid())

         insert (*root+, x, s);

     else if (x > tree[root].Mid())

         insert (*root+, x, s);

 }

 void query (int root, int s, int e)

 {

     if (tree[root].L == s && tree[root].R == e)

     {

         Min = min (Min, tree[root].Min);

         Max = max (Max, tree[root].Max);

         return ;

     }

     if (e <= tree[root].Mid())

         query (*root+, s, e);

     else if (s > tree[root].Mid())

         query (*root+, s, e);

     else

     {

         query (*root+, s, tree[root].Mid());

         query (*root+, tree[root].Mid()+, e);

     }

 }

 int main ()

 {

     int n, q, num;

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

     {

         build(, , n);

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

         {

             scanf ("%d", &num);

             insert (, i, num);

         }

         while (q --)

         {

             int s, e;

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

             Min = INF;

             Max = -INF;

             query (, s, e);

             printf ("%d\n", Max - Min);

         }

     }

     return ;

 }