#include <cstdio>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 200000;
int v[N];

struct node{
    long long bst, pref, suf, sum;
}aint[N*4];

const long long INF = -2e15;
int qlf, qrg, val;

node combine (node l, node r) {
	node res;
	res.sum = l.sum + r.sum;
	res.pref = max (l.pref, l.sum + r.pref);
	res.suf = max (r.suf, r.sum + l.suf);
	res.bst = max (max (l.bst, r.bst), l.suf + r.pref);
	return res;
}

void build(int pos, int lf, int rg){
    if(lf == rg){
        aint[pos].pref = v[lf];
        aint[pos].suf = v[lf];
        aint[pos].bst = v[lf];
        aint[pos].sum = v[lf];
        return;
    }
    int md = (lf + rg)/2;
    build(2 * pos, lf, md);
    build(2 * pos + 1, md + 1, rg);
    aint[pos] = combine(aint[2 * pos], aint[2 * pos + 1]);
}

node query(int pos, int lf, int rg){
	if(rg < qlf || lf > qrg){
		node t;
		t.bst = t.pref = t.suf = t.sum = INF;
		return t;
	}
    if(qlf <= lf && rg <= qrg){
        return aint[pos];
    }
    int md = (lf + rg)/2;
    return combine(query(2 * pos, lf, md), query(2 * pos + 1, md + 1, rg));
}

int main(){
    int n,i,q;
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    scanf("%d %d", &n, &q);
    for(i = 1;i <= n;i++){
        scanf("%d", &v[i]);
    }
    build(1, 1, n);
    for(i = 1;i <= q;i++){
        scanf("%d %d", &qlf, &qrg);
        printf("%lld\n", query(1, 1, n).bst);
    }
    return 0;
}