#include <stdio.h>

#define inf (int)1e9
#define nmax 200005
#define amax 524288

struct s_nod {
	int best_sum,total_sum,left_sum,right_sum;
};

int a[nmax],n,v1,v2,v3,m,i;
s_nod arb[amax];

inline int max(int a,int b) {
	if(a > b) return a;
	else return b;
}

void create(int nod,int l,int r) {
	if(l == r) arb[nod].best_sum = arb[nod].total_sum = arb[nod].left_sum = arb[nod].right_sum = a[l];
	else {
		int mi = (l + r) / 2;
		create(nod * 2,l,mi);
		create(nod * 2 + 1,mi + 1,r);
		arb[nod].total_sum = arb[nod * 2].total_sum + arb[nod * 2 + 1].total_sum;
		arb[nod].left_sum = max(arb[nod * 2].left_sum,arb[nod * 2].total_sum + arb[nod * 2 + 1].left_sum);
		arb[nod].right_sum = max(arb[nod * 2 + 1].right_sum,arb[nod * 2 + 1].total_sum + arb[nod * 2].right_sum);
		arb[nod].best_sum = max(arb[nod * 2].best_sum,max(arb[nod * 2 + 1].best_sum,arb[nod * 2].right_sum + arb[nod * 2 + 1].left_sum));
	}
}

void update(int nod,int l,int r,int poz) {
	if(l == r) arb[nod].best_sum = arb[nod].total_sum = arb[nod].left_sum = arb[nod].right_sum = a[l];
	else {
		int mi = (l + r) / 2;
		if(mi >= poz) update(nod * 2,l,mi,poz);
		else update(nod * 2 + 1,mi + 1,r,poz);
		arb[nod].total_sum = arb[nod * 2].total_sum + arb[nod * 2 + 1].total_sum;
		arb[nod].left_sum = max(arb[nod * 2].left_sum,arb[nod * 2].total_sum + arb[nod * 2 + 1].left_sum);
		arb[nod].right_sum = max(arb[nod * 2 + 1].right_sum,arb[nod * 2 + 1].total_sum + arb[nod * 2].right_sum);
		arb[nod].best_sum = max(arb[nod * 2].best_sum,max(arb[nod * 2 + 1].best_sum,arb[nod * 2].right_sum + arb[nod * 2 + 1].left_sum));
	}
}

s_nod query(int nod,int l,int r,int i,int j) {
	if(i <= l && j >= r) return arb[nod];
	else {
		s_nod aux,pa1,pa2;
		int mi = (l + r) / 2,p1 = 0,p2 = 0;
		if(mi >= i) {
			p1 = 1;
			pa1 = query(nod * 2,l,mi,i,j);
		}
		if(mi < j) {
			p2 = 1;
			pa2 = query(nod * 2 + 1,mi + 1,r,i,j);
		}
		aux.total_sum = 0; if(p1) aux.total_sum += pa1.total_sum; if(p2) aux.total_sum += pa2.total_sum;
		aux.left_sum = -inf; 
		if(p1 && p2) aux.left_sum = max(pa1.left_sum,pa1.total_sum + pa2.left_sum);
		else if(p1) aux.left_sum = max(aux.left_sum,pa1.left_sum);
		else if(p2) aux.left_sum = max(aux.left_sum,pa2.left_sum);
		aux.right_sum = -inf;
		if(p1 && p2) aux.right_sum = max(pa2.right_sum,pa2.total_sum + pa1.right_sum);
		else if(p2) aux.right_sum = pa2.right_sum;
		else if(p1) aux.right_sum = pa1.right_sum;
		aux.best_sum = aux.total_sum;
		if(p1 && p2) aux.best_sum = max(pa1.best_sum,max(pa2.best_sum,pa1.right_sum + pa2.left_sum));
		else if(p1) aux.best_sum = pa1.best_sum;
		else if(p2) aux.best_sum = pa2.best_sum;
		return aux;
	}
}

int main() {
/*	freopen("maxq.in","r",stdin);
	freopen("maxq.out","w",stdout);
*/
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);

	scanf("%d",&n);
	scanf("%d",&m);
	for(i = 1; i <= n; i++) scanf("%d",&a[i]);
	create(1,1,n);
	for(i = 1; i <= m; i++) {
		scanf("%d%d",&v1,&v2);
		printf("%d\n",query(1,1,n,v1,v2).best_sum);
	/*	scanf("%d%d%d",&v1,&v2,&v3);
		if(v1 == 0) {
			a[v2 + 1] = v3;
			update(1,1,n,v2 + 1);
		}
		else printf("%d\n",query(1,1,n,v2 + 1,v3 + 1).best_sum);*/
	}

	return 0;
}