#include <bits/stdc++.h>
using namespace std;
#define NMAX 100010 * 4
#define INF -1e9


struct node{
    int pref, suf, ssm, suma;
};

node aint[NMAX];
int  a[NMAX];

node _merge(node left, node right){
    node res;
    res.ssm = max(max(right.ssm, left.ssm), right.pref + left.suf);
    res.pref = max(left.pref, left.suma + right.pref);
    res.suf = max(right.suf, right.suma+ left.suf);
    res.suma = left.suma + right.suma;
    return res;
}




void build(int nod, int st, int dr){
    if(st == dr){
        aint[nod].pref = aint[nod].suf = aint[nod].ssm = aint[nod].suma = a[st];
    }else{
        int mid = (st + dr ) / 2;
        build(nod * 2, st, mid);
        build(nod * 2 + 1, mid + 1, dr);
        aint[nod] = _merge(aint[nod * 2], aint[nod * 2 + 1]);
    }
}
node sol;

void clearNode(node &nod){
    nod.ssm = nod.pref = nod.suf = INF;
    nod.suma = 0;
}

void query(int nod, int st, int dr, int left, int right){
    if(st >= left && dr <= right){
        sol = _merge(sol, aint[nod]);
       // cout << aint[nod].ssm << '\n';
    }else{
        int mid = (st + dr ) / 2;
        if(left <= mid){
            query(nod * 2, st, mid, left, right);
        }
        if(right > mid){
            query(nod * 2 +1, mid + 1, dr, left, right);
        }
    }
}


int main(void){
    ofstream cout("sequencequery.out");
    ifstream cin("sequencequery.in");
    int n,Q;
    cin >> n >> Q;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
    }
    build(1,1,n);
    while(Q--){
        int x, y;
        cin >> x >> y;
        clearNode(sol);
        query(1,1,n,x,y);
        cout << sol.ssm << '\n';
    }

}