#include<iostream> #include<cmath> #include<cstdio> #define N 50005 using namespace std; int maxx[N][20],minn[N][20],a[N]; int ST(int n) { for(int i=1;i<=n;i++) { maxx[i][0]=a[i]; minn[i][0]=a[i]; } for(int j=1;(1<<j)<=n;j++) { for(int i=1;i+(1<<j)-1<=n;i++) { maxx[i][j]=max(maxx[i][j-1],maxx[i+(1<<(j-1))][j-1]); minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]); } } } int main() { int n,q,lf,rg,mx,mn; cin>>n>>q; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } ST(n); for(int i=1;i<=q;i++) { scanf("%d %d",&lf,&rg); int k=log2(rg-lf+1); mx=max(maxx[lf][k],maxx[rg-(1<<k)+1][k]); mn=min(minn[lf][k],minn[rg-(1<<k)+1][k]); cout<<mx-mn<<endl; } }