#include <stdio.h>

#define inf (int)1e6
#define nmax 100001
#define vmax 300001
#define LL long long

struct cell {
	int total_sum,sum_left,sum_right,best_sum;
};

int a[nmax],n,m,i,v1,v2;
cell arb[vmax];

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

void create(int nod,int left,int right) {
	if(left == right) arb[nod].total_sum = arb[nod].sum_left = arb[nod].sum_right = arb[nod].best_sum = a[left];
	else {
		int mi = (left + right) / 2;
		create(nod * 2,left,mi);
		create(nod * 2 + 1,mi + 1,right);
		arb[nod].total_sum = arb[nod * 2].total_sum + arb[nod * 2 + 1].total_sum;
		arb[nod].sum_left = max(arb[nod * 2].sum_left,arb[nod * 2].total_sum + arb[nod * 2 + 1].sum_left);
		arb[nod].sum_right = max(arb[nod * 2 + 1].sum_right,arb[nod * 2 + 1].total_sum + arb[nod * 2].sum_right);
		arb[nod].best_sum = arb[nod].total_sum;
		arb[nod].best_sum = max(arb[nod].best_sum,arb[nod * 2].sum_right + arb[nod * 2 + 1].sum_left);
		arb[nod].best_sum = max(arb[nod].best_sum,arb[nod * 2].best_sum);
		arb[nod].best_sum = max(arb[nod].best_sum,arb[nod * 2 + 1].best_sum);
		arb[nod].best_sum = max(arb[nod].best_sum,arb[nod].sum_left);
		arb[nod].best_sum = max(arb[nod].best_sum,arb[nod].sum_right);
	}
}

cell query(int nod,int st,int dr,int left,int right) {
	int mi = 0,p1 = 0,p2 = 0;
	cell part1,part2;
	part1.total_sum = part1.sum_left = part1.sum_right = part1.best_sum = 0;
	part2.total_sum = part2.sum_left = part2.sum_right = part2.best_sum = 0;
	if(st >= left && dr <= right) return arb[nod];
	else {
		mi = (st + dr) / 2;
		if(mi >= left) {
			p1 = 1;
			part1 = query(nod * 2,st,mi,left,right);
		}
		if(mi < right) {
			p2 = 1;
			part2 = query(nod * 2 + 1,mi + 1,dr,left,right);
		}
		cell rez;
		rez.total_sum = -inf;
		if(p1) rez.total_sum = part1.total_sum;
		else if(p2) rez.total_sum = part2.total_sum;
		else if(p1 && p2) rez.total_sum = part1.total_sum + part2.total_sum;
		rez.sum_left = -inf;
		if(p1) rez.sum_left = part1.sum_left;
		if(p1 && p2) rez.sum_left = max(rez.sum_left,part1.total_sum + part2.sum_left);
		rez.sum_right = -inf;
		if(p2) rez.sum_right = part2.sum_right;
		if(p1 && p2) rez.sum_right = max(rez.sum_right,part2.total_sum + part1.sum_right);
		rez.best_sum = rez.total_sum;
		rez.best_sum = max(rez.best_sum,rez.sum_left);
		rez.best_sum = max(rez.best_sum,rez.sum_right);
		if(p1) rez.best_sum = max(rez.best_sum,part1.best_sum);
		if(p2) rez.best_sum = max(rez.best_sum,part2.best_sum);
		if(p1 && p2) rez.best_sum = max(rez.best_sum,part1.sum_right + part2.sum_left);
		return rez;
	}
}

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

	scanf("%d%d",&n,&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);
		cell ax = query(1,1,n,v1,v2);
		printf("%d\n",ax.best_sum);
	}

	return 0;
}