#include <iostream>
#include <cstdio>

#define N 100005

using namespace std;

struct Nod{
    long long val, prefix, sufix, total;
    Nod(){;}
    Nod(int _val){
        val = prefix = sufix = total = _val;
    }
}arbint[4*N];

int v[N], n, m, x, y;

Nod actualizareNod(Nod st, Nod dr){
    Nod r;

    r.total = st.total + dr.total;
    r.val = max(max(st.val,dr.val),
                st.sufix+dr.prefix);
    r.prefix = max(st.prefix, st.total + dr.prefix);
    r.sufix = max(dr.sufix, dr.total + st.sufix);

    return r;
}

void construieste(int st = 1, int dr = n, int pos = 1){
    if(st == dr){
        arbint[pos]=Nod(v[dr]);
        return;
    }

    int mij = (st+dr)/2;

    construieste(st,mij,2*pos);
    construieste(mij+1,dr,2*pos+1);

    arbint[pos] = actualizareNod(arbint[2*pos],arbint[2*pos+1]);
}

Nod cauta(int qst, int qdr, int st = 1, int dr = n, int pos = 1){
    if(qst<=st && dr<=qdr)
        return arbint[pos];

    int mij = (st+dr)/2;

    if(qdr<=mij)
        return cauta(qst,qdr,st,mij,2*pos);
    if(mij<qst)
        return cauta(qst,qdr,mij+1,dr,2*pos+1);

    return actualizareNod(cauta(qst,qdr,st,mij,2*pos),
                    cauta(qst,qdr,mij+1,dr,2*pos+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]);

    construieste();

    for(int i=0;i<m;++i){
        scanf("%d%d", &x,&y);
        cout<<cauta(x,y).val<<"\n";
    }

    return 0;
}