#include <cstdio>
#include <algorithm>
using namespace std;
struct Interval
{
    long long secvsum,sumpre,sumsuff,sum;
};
int v[100005];
Interval arbint[1<<18];
int n;
Interval create(int value)
{
    return Interval{
        value,
        value,
        value,
        value,
    };
}
Interval join(const Interval &left, const Interval &right)
{
    return Interval{
        max(max(left.secvsum, right.secvsum),left.sumsuff+right.sumpre),
        max(left.sumpre, left.sum+right.sumpre),
        max(right.sumsuff, left.sumsuff+right.sum),
        left.sum+right.sum,
    };
}
void build(int nod, int st, int dr)
{
    if(st==dr)
        arbint[nod]=create(v[st]);
    else{
        int mij=(st+dr)/2;
        build(2*nod, st, mij);
        build(2*nod+1, mij+1, dr);
        arbint[nod]=join(arbint[2*nod], arbint[2*nod+1]);
    }
}
void build()
{
    build(1, 1, n);
}
Interval query(int nod, int st, int dr, int left, int right)
{
    if(st==left && dr==right)
        return arbint[nod];
    else{
        int mij=(st+dr)/2;
        if(right<=mij)
            return query(2*nod, st, mij, left, right);
        else{
            if(mij<left)
                return query(2*nod+1, mij+1, dr, left, right);
            else
                return join(query(2*nod, st, mij, left, mij), query(2*nod+1, mij+1, dr, mij+1, right));
        }
    }
}
Interval query(int left, int right)
{
    return query(1, 1, n, left, right);
}
int main()
{   freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    int m,i,x,y;
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++)
        scanf("%d", &v[i]);
    build();
    for(i=1; i<=m; i++){
        scanf("%d%d", &x, &y);
        printf("%lld\n", query(x, y).secvsum);
    }
    return 0;
}