#include<bits/stdc++.h>
using namespace std;
long long input[500010];
long long n,m,x,y,z,ans;
char a;
struct tree{
	long long l,r,sum;
}tree[2000010];
void build(long long i,long long left,long long right){
	tree[i].l=left;
	tree[i].r=right;
	if(left==right){
		tree[i].sum=input[tree[i].l];
		return ;
	}
	long long mid=(left+right)/2;
	build(i*2,left,mid);
	build(i*2+1,mid+1,right);
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
}
long long function_a(long long i,long long l,long long r){
	if(tree[i].l==tree[i].r){
		return tree[i].sum;
	}
	long long mid=(tree[i].l+tree[i].r)/2,ans=-1;
	if(mid>=l) ans=max(ans,function_a(i*2,l,r));
	if(mid<r) ans=max(ans,function_a(i*2+1,l,r));
	return ans;
}
long long function_b(long long i,long long l,long long r){
	if(tree[i].l==tree[i].r){
		return tree[i].sum;
	}
	long long mid=(tree[i].l+tree[i].r)/2,ans=1000010;
	if(mid>=l) ans=min(ans,function_b(i*2,l,r));
	if(mid<r) ans=min(ans,function_b(i*2+1,l,r));
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%d",&input[i]);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
	    cout<<function_a(1,x,y)-function_b(1,x,y)<<endl;
	}
	return 0;
}