#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];
long long a,b,ans,S;

struct op
{
    long long S,D,B,SUM;
}T[3*Dim];

void Build(int nod,int st,int dr)
{
    if(st==dr)
    {
        T[nod].S=T[nod].D=T[nod].SUM=T[nod].B=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;
    T[nod].S=max(T[rs].S,T[rd].S+T[rs].SUM);
    T[nod].D=max(T[rd].D,T[rd].SUM+T[rs].D);
    T[nod].B=max(T[rs].B,max(T[rd].B,T[rs].D+T[rd].S));
    T[nod].SUM=T[rs].SUM+T[rd].SUM;
}

void query(int nod,int st,int dr)
{
    if(st>=a&&dr<=b)
    {
        ans=max(ans,max(T[nod].B,S+T[nod].S));
        S=max(S+T[nod].SUM,T[nod].D);
        return ;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
    query(2*nod,st,mij);
    if(b>=mij+1)
    query(2*nod+1,mij+1,dr);


}



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