#include<fstream>

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

struct Str{
    long long L,R,M,S;
} A[400010];

int V[100003],N,M;

void Build(int Nod,int L,int R){
    if(L==R){
        A[Nod].L=V[L];
        A[Nod].R=V[L];
        A[Nod].M=V[L];
        A[Nod].S=V[L];
        return;
    }
    int M=(L+R)/2;
    int LSon=2*Nod,RSon=2*Nod+1;
    Build(LSon,L,M);
    Build(RSon,M+1,R);
    A[Nod].S=A[LSon].S+A[RSon].S;
    A[Nod].L=max(A[LSon].L,A[LSon].S+A[RSon].L);
    A[Nod].R=max(A[RSon].R,A[RSon].S+A[LSon].R);
    A[Nod].M=max(max(A[LSon].M,A[RSon].M),A[LSon].R+A[RSon].L);
}

void Query(int Nod,int L,int R,int QL,int QR,long long& Best,long long& Ans){
    if(QR<L || QL>R)
        return;
    if(QL<=L && QR>=R){
        Ans=max(Ans,max(A[Nod].M,Best+A[Nod].L));
        Best=max(Best+A[Nod].S,A[Nod].R);
        return;
    }
    int M=(L+R)/2;
    int LSon=2*Nod,RSon=2*Nod+1;

    Query(LSon,L,M,QL,QR,Best,Ans);
    Query(RSon,M+1,R,QL,QR,Best,Ans);
}

int main()
{
    fin>>N>>M;
    for(int i=1;i<=N;i++)
        fin>>V[i];
    Build(1,1,N);
    for(int i=1;i<=M;i++){
        int X,Y;
        fin>>X>>Y;
        long long Ans=-20000000000000,Best=-20000000000000;
        Query(1,1,N,X,Y,Best,Ans);
        fout<<Ans<<'\n';
    }
}