[AppleScript] syntaxhighlighter_viewsource syntaxhighlighter_copycode
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m;
int Min[50001][32],Max[50001][32];
int main(){
int a,b;
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%d",&Min[0]);
Max[0]=Min[0];
}
for(int j=1;j<=floor(log2(n));j++){
for(int i=1;i<=n-(1<<j)+1;i++){
Max[j]=max(Max[j-1],Max[i+(1<<(j-1))][j-1]);
Min[j]=min(Min[j-1],Min[i+(1<<(j-1))][j-1]);
}
}
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
int k=floor(log2(b-a+1));
printf("%d\n",max(Max[a][k],Max[b-(1<<k)+1][k])-min(Min[a][k],Min[b-(1<<k)+1][k]));
}
}