1
#include<bits/stdc++.h>
2
using namespace std;
3
const int N=5e5+10,inf=2e9;
4
int n,q,i,l,r,T_min[N],T_max[N],a[N];
5
int lowbit(int x){return x&(-x);}
6
void Add(int p,int v){while(p<=n)T_min[p]=min(T_min[p],v),T_max[p]=max(T_max[p],v),p+=lowbit(p);}
7
int Query_min(int l,int r){return (l<r?(l<r-lowbit(r)?min(T_min[r],Query_min(l,r-lowbit(r))):min(a[r],Query_min(l,r-1))):a[l]);}
8
int Query_max(int l,int r){return (l<r?(l<r-lowbit(r)?max(T_max[r],Query_max(l,r-lowbit(r))):max(a[r],Query_max(l,r-1))):a[l]);}
9
int main(){
10
 cin>>n>>q;
11
 for(i=0;i<N;i++)T_min[i]=inf,T_max[i]=-inf;
12
 for(i=1;i<=n;i++)cin>>a[i],Add(i,a[i]);
13
 while(q--)cin>>l>>r,cout<<Query_max(l,r)-Query_min(l,r)<<'\n';
14
}