#include <cstdio>
const int N = 100005;
struct tip{long long st, dr, s, subs;} v[N * 4];

const long long INF = 0x3f3f3f3f;
int n, m, p1, p2, a[N];
long long rez, val;

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

void update(int st, int dr, int poz) {
//	if(st != 0 && dr != 0)
//		fprintf(stderr, "%d %d %d\n", st, dr, poz);
	if(st == dr) {
		v[poz].subs = v[poz].st = v[poz].dr = v[poz].s =(long long) a[st];
		return;
	}

	int x = (st + dr) / 2 ;

	update(st, x, poz * 2);
	update(x + 1, dr, poz * 2 + 1);

	v[poz].s = v[poz * 2].s + v[poz * 2 + 1].s;
	v[poz].st = max(v[poz * 2].st, v[poz * 2 + 1].st + v[poz * 2].s);
	v[poz].dr = max(v[poz * 2 + 1].dr, v[poz * 2 + 1].s + v[poz * 2].dr);
	v[poz].subs = max(v[poz * 2].subs, v[poz * 2 + 1].subs);
	v[poz].subs = max(v[poz].subs, v[poz * 2].dr + v[poz * 2 +1].st);
}

void query(int st, int dr, int poz) {
	if(st > p2 || dr < p1)
		return ;
	
	if(p1 <= st && dr <= p2) {
		long long rem = v[poz].subs;
		rem = max(rem, v[poz].st + val);
		val = max(val + v[poz].s, v[poz].dr);
		rez = max(rez, rem);
		return ;
	}

	int x = (st + dr) >> 1;

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

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

	scanf("%d %d", &n, &m);
	for(i = 1; i <= n; ++i)
		scanf("%d" ,&a[i]);

	update(1, n, 1);
//	return 0;
	for(i = 1; i <= m; ++i) {
		scanf("%d %d", &p1, &p2);
		val  = 0;
		rez = -INF;
		query(1, n, 1);
		printf("%lld\n", rez);
	}

	return 0;
}