#include <stdio.h>
#include <mem.h>
#define MAXN (1<<18)+1
#define INF 10000000001ll
#define Min(a, b) (a)<(b)?(a):(b)
#define Max(a, b) (a)>(b)?(a):(b)

long long min[MAXN], max[MAXN], sum[MAXN], secv[MAXN], x, a, b, S, min_ant, poz;

void 	update(int st, int dr, int nod){
	if(st==dr) {
		max[nod]=sum[st];
		min[nod]=sum[st-1];
		secv[nod]=x;
	}
	else{
		int m=(st+dr)>>1;
		if(poz<=m) update(st, m, 2*nod);
		else update(m+1, dr, 2*nod+1);
		min[nod] = Min(min[2*nod], min[2*nod+1]);
		max[nod] = Max(max[2*nod], max[2*nod+1]);
		secv[nod] = Max( Max(secv[2*nod], secv[2*nod+1]), max[2*nod+1]-min[2*nod]);
	}
}

void query(int st, int dr, int nod){
	if(a<=st && dr<=b){
		S = Max(S, secv[nod]);
		if(min_ant!=INF)
			S = Max(S, max[nod]-min_ant);
		if(min_ant > min[nod]) min_ant = min[nod];
	}
	else{
		int m=(st+dr)>>1;
		if(a<=m) query(st, m, 2*nod);
		if(b>m) query(m+1, dr, 2*nod+1);
	}
}


int main(){
	FILE *f=fopen("sequencequery.in", "r");
	FILE *g=fopen("sequencequery.out", "w");
	int i, n, m;
	fscanf(f, "%d %d", &n, &m);

	for(i=1; i<=n; i++){
		fscanf(f, "%lld", &x);
		poz=i;
		sum[i] = sum[i-1]+x;
		update(1, n, 1);
	}

	for(i=0; i<m; i++){
		fscanf(f, "%d %d", &a, &b);
		S=-INF; min_ant=INF;
		query(1, n, 1);
		fprintf(g, "%lld\n", S);
	}
	return 0;
}