#include <fstream>

using namespace std;

ifstream in("sequencequery.in");
ofstream out("sequencequery.out");

const int N=100001;
const int INF=1<<30;

int s[N],n,m,minim[N*15],maxim[N*15],minsecv,maxsecv,x,y;

void read(){
	int aux,i;
	in>>n>>m;
	for(i=1;i<=n;++i){
		in>>aux;
		s[i]=s[i-1]+aux;
	}
}

inline int min(int a,int b){return a<b ? a: b;}
inline int max(int a,int b){return a>b ? a: b;}

void BuildTree(int st,int dr,int poz){
	int m;
	if(st==dr){
		minim[poz]=s[st-1];
		maxim[poz]=s[st];
		return;
	}
	m=(st+dr)/2;
	BuildTree(st,m,2*poz);
	BuildTree(m+1,dr,2*poz+1);
	maxim[poz]=max(maxim[2*poz+1],maxim[2*poz]);
	minim[poz]=min(minim[2*poz+1],minim[2*poz]);
}

void query(int st,int dr,int poz){
	int m=(st+dr)/2;
	if(st>=x && dr<=y){
		if(maxsecv<maxim[poz])
			maxsecv=maxim[poz];
		if(minsecv>minim[poz])
			minsecv=minim[poz];
		return;
	}
	if(x<=m){
		query(st,m,2*poz);
	}
	if(y>=m+1){
		query(m+1,dr,2*poz+1);
	}
}
	
	
void Solve(){
	int i;
	for(i=1;i<=m;i++){
		in>>x>>y;
		minsecv=INF;
		maxsecv=-INF;
		query(1,n,1);
		out<<maxsecv-minsecv<<"\n";
	}
}
	
int main(){
	read();
	BuildTree(1,n,1);
	Solve();
	return 0;
}