#include <fstream>
#define FOR(i,x) for (i=1;i<=x;i++)
#define ll long long
#define max(a,b) ((a>b) ? a : b)
using namespace std;
struct contain{ll left;ll right;ll seq;ll all;};
contain T[1000001];
ll start,finish,rezultat,aux,N,Q,a[100002],i;
void Update(int nod,int st,int dr)
{
    if (st==dr)
    {
        T[nod].left=T[nod].right=T[nod].seq=T[nod].all=a[dr];
        return;
    }
    int m=(st+dr)/2;
    Update(nod*2,st,m);
    Update(nod*2+1,m+1,dr);
    T[nod].all=T[nod*2].all+T[nod*2+1].all;
    T[nod].left=max(T[nod*2].left,T[nod*2].all+T[nod*2+1].left);
    T[nod].right=max(T[nod*2+1].right,T[nod*2+1].all+T[nod*2].right);
    T[nod].seq=max(max(max(T[nod].left,T[nod].right),max(T[2*nod].seq,T[2*nod+1].seq)),T[nod*2].right+T[nod*2+1].left);
}
void Query(int nod,int st,int dr)
{
    if (start<=st&&dr<=finish)
    {
        rezultat=max(rezultat,T[nod].seq);
        rezultat=max(rezultat,aux+T[nod].left);
        aux=max(aux+T[nod].all,T[nod].right);
        aux=max(aux,0LL);
        return;
    }
    int m=(st+dr)/2;
    if (start<=m) Query(nod*2,st,m);
    if (finish>m) Query(nod*2+1,m+1,dr);
}
int main()
{
    ifstream f("sequencequery.in");
    ofstream g("sequencequery.out");
    f>>N>>Q;
    FOR(i,N) f>>a[i];
    Update(1,1,N);
    while (Q--)
    {
        f>>start>>finish;
        rezultat=aux=-9999999999LL;
        Query(1,1,N);
        g<<rezultat<<'\n';
    }
    return 0;
}