#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 int a[maxn];

 int nmax,nmin;

 struct node{

     int l,r;//记录区间的左右端点

     int nmax,nmin;//记录区间的最大值，最小值

 };

 node tree[*maxn];

 void build_tree(int i,int l,int r){//建树

     tree[i].l=l;

     tree[i].r=r;

     if(l==r){

         tree[i].nmin=tree[i].nmax=a[l];

         return;

     }

     int mid=(l+r)/;

     build_tree(*i,l,mid);

     build_tree(*i+,mid+,r);

     tree[i].nmin=min(tree[*i].nmin,tree[*i+].nmin);

     tree[i].nmax=max(tree[*i].nmax,tree[*i+].nmax);

 }

 void query(int i,int l,int r){//查询

     if(tree[i].nmin>=nmin&&tree[i].nmax<=nmax) return;

     if(tree[i].l==l&&tree[i].r==r){

         nmin = min(tree[i].nmin,nmin);

         nmax = max(tree[i].nmax,nmax);

         return;

     }

     int mid=(tree[i].l+tree[i].r)/;

     if(r<=mid) query(*i,l,r);

     else if(l>mid) query(*i+,l,r);

     else{

         query(*i,l,mid);

         query(*i+,mid+,r);

     }

 }

 int main(){

     int n,q;

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

         for(int i=;i<=n;i++) scanf("%d",&a[i]);

         build_tree(,,n);

         while(q--){

             nmin=INF;nmax=-INF;

             int l,r;

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

             query(,l,r);

             printf("%d\n",nmax-nmin);

         }

     }

     return ;

 }