#include<stdio.h>

#define lg 100003

int n, m, i, x, init[lg], poz, p1, p2, l2, rsp;

struct sgtree{
	int x, y, sm, rp;
};
sgtree q[3*lg];

inline int max(int a, int b){
	return a > b ? a : b;
}

void cstr(int st, int dr, int poz){
	if (st == dr){
		init[st] = poz;
		return ;
	}

	int x = (st+dr) / 2;

	cstr(st, x, 2*poz);
	cstr(x+1, dr, 2*poz+1);
}
void update(int poz){
	for (; poz; poz /= 2){
		q[poz].sm = q[2*poz].sm + q[2*poz+1].sm;
		q[poz].x = max(q[2*poz].x, q[2*poz].sm + q[2*poz+1].x);
		q[poz].y = max(q[2*poz+1].y, q[2*poz+1].sm + q[2*poz].y);
		q[poz].rp = max(q[2*poz].rp, q[2*poz+1].rp); q[poz].rp = max(q[poz].rp, q[2*poz].y + q[2*poz+1].x);
	}
}
void query(int st, int dr, int poz){
	if (st >= p1 && dr <= p2){
		//printf("%d %d -> ", st, dr);
		rsp = max(rsp, q[poz].rp); rsp = max(rsp, l2 + q[poz].x);
		l2 = max(q[poz].y, l2 + q[poz].sm);

		//printf("%d %d\n", rsp, l2);

		return ;
	}
	if (st > p2 || dr < p1 || st == dr)
		return ;

	int x = (st+dr) / 2;
	query(st, x, 2*poz);
	query(x+1, dr, 2*poz+1);
}

int main()
{
	freopen("sequencequery.in", "rt", stdin);
	freopen("sequencequery.out", "wt", stdout);

	scanf("%d%d", &n, &m);
	cstr(1, n, 1);

	for (i = 1; i <= n; i ++){
		scanf("%d", &x);

		poz = init[i];
		q[poz].x = q[poz].y = q[poz].rp = q[poz].sm = x;

		update(poz / 2);
	}

	for (i = 1; i <= m; i ++){
		scanf("%d%d", &p1, &p2);

		rsp = -0x3f3f3f3f, l2 = -0x3f3f3f3f;
		query(1, n, 1);

		printf("%d\n", rsp);
	}
	
	return 0;
}