#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*2],maxim[N*2],bestsecv,x,y,best[N*2],minaux[N],maxaux[N],auxsize;

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,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];
		auxsize++;
		minaux[auxsize]=minim[poz];
		maxaux[auxsize]=maxim[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;
		auxsize=0;
		query(1,n,1);
		for(j=1;j<=auxsize;++j)
			for(k=j;k<=auxsize;++k)
				if(maxaux[k]-minaux[j]>bestsecv)
					bestsecv=maxaux[k]-minaux[j];
		out<<bestsecv<<"\n";
	}
}
	
int main(){
	read();
	BuildTree(1,n,1);
	Solve();
	return 0;
}