#include<stdio.h>

 #include<algorithm>

 #define inf 0x3f3f3f3f

 using namespace std;

 int n, m, arr[];

 int ansmax, ansmin;

 struct Tree

 {

     int maxx, minn, left, right; //记录区间信息

 }tree[ * ]; //开四倍空间 

 void build(int left, int right, int k)

 {

     tree[k].left = left, tree[k].right = right; //区间左右

     if(tree[k].left == tree[k].right)

     {

         tree[k].maxx = tree[k].minn = arr[left]; //分到最后只剩下一个值 记为最大最小值

         return ;

     }

     int mid = (left + right)/;

     build(left, mid, k * ); //往左右儿子构造线段树

     build(mid + , right, k *  + );

     tree[k].maxx = max(tree[k * ].maxx, tree[k *  + ].maxx); //满足区间相加.子区间之间的最大最小值也是父亲区间的最大最小值

     tree[k].minn = min(tree[k * ].minn, tree[k *  + ].minn);

 }

 void query(int k, int left, int right, int find_left, int find_right)

 {  //如果ansmax已经大于等于该点区间最大值,ansmin已经小于等于该点区间最小值 , 不用更新,return

     if(ansmax >= tree[k].maxx && ansmin <= tree[k].minn)

         return ;

     if(find_left == left && find_right == right)

     {  //查询区间刚好是某个节点的区间, 该区间已经记录了最大最小值信息,可以直接调用并return

         ansmax = max(ansmax, tree[k].maxx);

         ansmin = min(ansmin, tree[k].minn);

         return ;

     }

     int mid = (left + right)/;

     if(find_right <= mid) //查询区间全位于该节点的左儿子区间

         query( * k, left, mid, find_left, find_right);

     else if(find_left > mid)//查询区间全位于该节点的右儿子区间

         query( * k + , mid + , right, find_left, find_right);

     else

     {  //有位于左儿子和右儿子部分

         query( * k, left, mid, find_left, mid);

         query( * k + , mid + , right, mid + , find_right);

     }

 }

 int main()

 {

     int a, b;

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

     for(int i = ; i <= n; i ++)//线段树根节点从1开始 ,数组从1开始存

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

     build(, n, );

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

     {

         ansmax = -inf;

         ansmin = inf;

         scanf("%d%d", &a, &b);

         query(, , n, a, b);

         printf("%d\n", ansmax - ansmin);

     }

     return ;

 }