#include <stdio.h>
#include <algorithm>
using namespace std;
#define NMAX 100010
#define INF 2000000000
long long S[NMAX*3], dr[NMAX*3], st[NMAX*3], t[NMAX*3];
int v[NMAX];
int n, m, a, b;
long long sol;
long long sum, s;
void constr(int p, int q, int i){
	if(p == q){
		S[i] = dr[i] = st[i] = t[i] = v[p];
		return;
	}
	int m = (p+q)>>1;
	constr(p, m, 2*i);
	constr(m+1, q, 2*i+1);
	S[i] = S[2*i] + S[2*i+1];
	st[i] = max(st[2*i], S[2*i] + st[2*i+1]);
	dr[i] = max(dr[2*i+1], S[2*i+1] + dr[2*i]);
	t[i] = max( max(t[2*i], t[2*i+1]), max(st[i], dr[i]));
	t[i] = max(t[i], dr[2*i] + st[2*i+1]);
}
void query(int p, int q, int i){
	if(a <= p && q <= b){
		sol = max(sol, sum + st[i]);
		sol = max(sol, t[i]);
		sum = max(sum + S[i], dr[i]);
		sum = max(sum, (long long)0);
		return ;
	}
	int m = (p+q)>>1;
	if(a <= m) query(p, m, 2*i);
	if(b > m) query(m+1, q, 2*i+1);
}
int main(){
	freopen("sequencequery.in", "r", stdin);
	freopen("sequencequery.out" ,"w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &v[i]);
	constr(1, n, 1);
	for(int i = 1; i <= m; ++i){
		scanf("%d%d", &a, &b);
		sol = -INF;
		sum = 0;
		query(1, n, 1);
		printf("%lld\n", sol);
	}
	return 0;
}