#include <fstream>
#include <algorithm>

using namespace std;

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

typedef long long I64;

const int NMAX = 200000;

struct SUMA{
    I64 sum, pre, suf, ssm;
};

I64 N,M;
int NR= 0;
SUMA arb[4*NMAX+1];
SUMA Ans_Q;

void recompute( SUMA &A, SUMA X, SUMA Y ) {
    A.sum = X.sum + Y.sum;
    A.suf = max( Y.suf , X.suf+Y.sum );
    A.pre = max( X.pre , X.sum+Y.pre );
    A.ssm = max( X.suf+Y.pre , max( X.ssm, Y.ssm ) );
}

void Update( I64 nod, I64 st, I64 dr, I64 poz, I64 val ) {
    if( st == dr ) {   ///  Am ajuns intr-o frunza
        arb[nod].sum= val;
        arb[nod].pre= val;
        arb[nod].suf= val;
        arb[nod].ssm= val;
    }
    else {  ///  Vad unde ma duc
        I64 mid= (st+dr)/2;
        if( poz <= mid ) {
            Update( 2*nod, st, mid, poz, val );
        }
        else {
            Update( 2*nod+1, mid+1, dr, poz, val );
        }
        ///  Actualizare
        recompute( arb[nod], arb[2*nod], arb[2*nod+1] );
    }
}

void Querry( I64 nod, I64 st, I64 dr, I64 x, I64 y ) {
    if( st >= x && y >= dr ) {
        ++NR;
        if( NR > 1 )  recompute( Ans_Q, Ans_Q, arb[nod] );
        else {
            Ans_Q= arb[nod];
        }
        return;
    }

    I64 mid= (st+dr)/2;
    if( x <= mid ) {
        Querry( 2*nod, st, mid, x, y );
    }
    if( y > mid ) {
        Querry( 2*nod+1, mid+1, dr, x, y );
    }
}

void Next_I64( I64 &x ) {
    x= 0;
    char c;
    int semn= 1;
    while( c!='-' && (c<'0'||c>'9')  )  in.get(c);
    if( c == '-' ){
        semn= -1;
        in.get(c);
    }
    while( c>='0' && c<='9' ) {
        x= x*10+c-'0';
        in.get(c);
    }
    x*= semn;
}



int main() {
    in >> N >> M;
    for( int i= 1;  i<=N;  ++i ) {
        I64 a;
        in >> a;
        Update( 1, 1,N, i,a );
    }
    for( int i= 1;  i<=M;  ++i ) {
        I64 x,y;
        in >> x >> y;

        NR= 0;
        Ans_Q.pre= Ans_Q.ssm= Ans_Q.suf= Ans_Q.sum= 0;
        Querry( 1, 1,N, x,y );
        out << Ans_Q.ssm << '\n';
    }
    return 0;
}