#include <fstream>
#define dim 100000
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

int v[dim+1];
struct node{
    long long s, sfx, pfx, smax;
}tree[4*dim+1];

node update_nod(node st, node dr)
{
    node crt;
    crt.s=st.s+dr.s;
    crt.pfx=max(st.pfx, st.s+dr.pfx);
    crt.sfx=max(dr.sfx, dr.s+st.sfx);
    crt.smax=max(st.sfx+dr.pfx, max(st.smax, dr.smax));
    return crt;
}

void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        tree[nod]={v[st], v[st], v[st], v[st]};
    }
    else
    {
        int mid=(st+dr)/2;
        build(2*nod, st, mid);
        build(2*nod+1, mid+1, dr);
        tree[nod]=update_nod(tree[2*nod], tree[2*nod+1]);
    }
}

node query(int nod, int st, int dr, int ql, int qr)
{
    if(ql<=st&&dr<=qr)
    {
        return tree[nod];
    }
    else
    {
        int mid=(st+dr)/2;
        if(qr<=mid)
        {
            return query(2*nod, st, mid, ql, qr);
        }
        if(mid<ql)
        {
            return query(2*nod+1, mid+1, dr, ql, qr);
        }
        node left, right;
        left=query(2*nod, st, mid, ql, qr);
        right=query(2*nod+1, mid+1, dr, ql, qr);
        return update_nod(left, right);
    }
}

int main()
{
    int x, y, n, m, i;
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>v[i];
    }
    build(1, 1, n);
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        fout<<query(1, 1, n, x, y).smax<<"\n";
    }
}