#include <fstream>
#define Nmax 400100
#define oo (1<<30)
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;

struct nod{int A,B,C,Sum;}Arb[Nmax];
int N,M,Ans,nAns;

void Query(int Nod,int Left,int Right,int x,int y) {

    if(x<=Left&&Right<=y) {
        if(nAns<0)
            nAns=0;
        Ans=max(Ans,max(nAns+Arb[Nod].A,Arb[Nod].C));
        nAns=max(nAns+Arb[Nod].Sum,Arb[Nod].B);
        return;
        }

    int Mid=(Left+Right)>>1;

    if(x<=Mid)  Query(2*Nod,Left,Mid,x,y);
    if(y>Mid)   Query(2*Nod+1,Mid+1,Right,x,y);

}
void Update(int Nod,int K,int Left,int Right,int Val) {

    if(Left==Right) {
        Arb[Nod].A=Arb[Nod].B=Arb[Nod].C=Arb[Nod].Sum=Val;
        return;
        }

    int Mid=(Left+Right)>>1;

    if(K<=Mid)  Update(2*Nod,K,Left,Mid,Val);
    else        Update(2*Nod+1,K,Mid+1,Right,Val);

    Arb[Nod].A=max(Arb[2*Nod].A,Arb[2*Nod].Sum+Arb[2*Nod+1].A);
    Arb[Nod].B=max(Arb[2*Nod+1].B,Arb[2*Nod+1].Sum+Arb[2*Nod].B);
    Arb[Nod].C=max(max(Arb[2*Nod].C,Arb[2*Nod+1].C),Arb[2*Nod].B+Arb[2*Nod+1].A);

    Arb[Nod].Sum=Arb[2*Nod].Sum+Arb[2*Nod+1].Sum;

}
void Read(ifstream & in) {

    int i,x;

    in>>N>>M;
    for(i=1;i<=N;i++)
        in>>x,Update(1,i,1,N,x);

}
void Solve(ifstream & in,ofstream & out) {

    int x,y;

    while(M--) {

        in>>x>>y;
        Ans=nAns=-oo;
        Query(1,1,N,x,y);
        out<<Ans<<'\n';
        }

}
int main() {

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

    Read(in);
    Solve(in,out);

    in.close();
    out.close();

    return 0;

}