#include <fstream>

using namespace std;

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

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

long long s[N],n,m,minim[N*3],maxim[N*3],minimpre,bestsecv,x,y,best[N*2];

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

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

void BuildTree(int st,int dr,int poz){
	int m;
	long long aux;
	if(st==dr){
		minim[poz]=s[st-1];
		maxim[poz]=s[st];
		best[poz]=s[st]-s[st-1];
		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]);
	aux=maxim[2*poz+1]-minim[2*poz];
	if(aux>max(best[2*poz],best[2*poz+1])){
		best[poz]=aux;
		return;
	}
	if(best[2*poz]>best[2*poz+1]){
		best[poz]=best[2*poz];
		return;
	}
	best[poz]=best[2*poz+1];
}

void query(int st,int dr,int poz){
	int m=(st+dr)/2;
	if(st>=x && dr<=y){
		if(best[poz]>bestsecv)
			bestsecv=best[poz];
		if(minimpre!=INF){
			if(bestsecv<maxim[poz]-minimpre)
				bestsecv=maxim[poz]-minimpre;
			minimpre=min(minimpre,minim[poz]);
		}
		else{
			minimpre=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,j,k;
	for(i=1;i<=m;i++){
		in>>x>>y;
		bestsecv=-INF;
		minimpre=INF;
		query(1,n,1);
		out<<bestsecv<<"\n";
	}
}
	
int main(){
	read();
	BuildTree(1,n,1);
	Solve();
	return 0;
}