#include <bits/stdc++.h>
#define Dim 100008
#define Min -10000000009
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
long long N,M,V[Dim],TS[2*Dim],TD[2*Dim],TB[2*Dim],TSUM[2*Dim];
long long a,b,ans,add,AUX[2*Dim];

void Build(int nod,int st,int dr)
{
    if(st==dr)
    {
        TS[nod]=TD[nod]=TSUM[nod]=TB[nod]=V[st];
        return;
    }
    int mij=(st+dr)/2;
    Build(2*nod,st,mij);
    Build(2*nod+1,mij+1,dr);
    int rs=2*nod,rd=rs+1;
    TS[nod]=max(TS[rs],TS[rd]+TSUM[rs]);
    TD[nod]=max(TD[rd],TSUM[rd]+TD[rs]);
    TB[nod]=max(TB[rs],max(TB[rd],TD[rs]+TS[rd]));
    TSUM[nod]=TSUM[rs]+TSUM[rd];
}

int  query(int nod,int st,int dr)
{
    if(st>=a&&dr<=b)
    {
        ans=max(ans,TB[nod]);
        return nod;
    }
    int mij=(st+dr)/2,A,B;
    bool decia=0,decib=0;
    if(a<=mij)
    {
        A=query(2*nod,st,mij);
        decia=1;
    }
    if(b>=mij+1)
    {
        B=query(2*nod+1,mij+1,dr);
        decib=1;
    }
    if(decia==1&&decib==0)
    {
        ans=max(ans,TB[A]);
        return A;
    }
    else
    if(decia==0&&decib==1)
    {
        ans=max(ans,TB[B]);
        return B;
    }
    else
    if(decia==1&&decib==1)
    {
        long long aux=max(TB[A],max(TB[B],TD[A]+TS[B]));
        ans=max(ans,aux);
        return nod;
    }
    return 0;

}

int main()
{
    f>>N>>M;
    for(int i=1;i<=N;i++) f>>V[i];
    Build(1,1,N);
    TB[0]=TS[0]=TD[0]=Min;
    for(int i=1;i<=M;i++)
    {
        f>>a>>b;
        ans=Min;
        query(1,1,N);
        g<<ans<<'\n';
    }
    return 0;
}