#include <algorithm>
#include <fstream>

using namespace std;

const int Dim = 100001;
const int Inf = 0x3f3f3f3f;

int N, M;
int ans, aux, aint_sm[Dim << 2], aint_sum[Dim << 2], aint_smst[Dim], aint_smdr[Dim];

void Upd( int nod, int st, int dr, int p, int a ) {

    int fs, fd, mj;

    if( st == dr ) {

        aint_sm[nod] = a;
        aint_sum[nod] = a;
        aint_smst[nod] = a;
        aint_smdr[nod] = a;

        return;
    }

    fs = nod << 1;
    fd = fs | 1;
    mj = (st + dr) >> 1;

    if( p <= mj )
        Upd( fs, st, mj, p, a );
    else
        Upd( fd, mj + 1, dr, p, a );

    aint_sm[nod] = max( aint_smdr[fs] + aint_smst[fd], max( aint_sm[fs], aint_sm[fd] ) );
    aint_sum[nod] = aint_sum[fs] + aint_sum[fd];
    aint_smst[nod] = max( aint_smst[fs], aint_sum[fs] + aint_smst[fd] );
    aint_smdr[nod] = max( aint_smdr[fd], aint_sum[fd] + aint_smdr[fs] );
}

void Que( int nod, int st, int dr, int x, int y ) {

    int fs, fd, mj;

    if( x <= st && dr <= y ) {

        if( aux < 0 )
            aux = 0;
        ans = max( ans, max( aux + aint_smst[nod], aint_sm[nod] ) );
        aux = max( aux + aint_sum[nod], aint_smdr[nod] );

        return;
    }

    fs = nod << 1;
    fd = fs | 1;
    mj = (st + dr) >> 1;

    if( x <= mj )
        Que( fs, st, mj, x, y );
    if( y > mj )
        Que( fd, mj + 1, dr, x, y );
}

int main() {

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

    int i, x, y;

    fin >> N;
    fin >> M;
    for( i = 1; i <= N; ++i ) {

        fin >> x;
        Upd( 1, 1, N, i, x );
    }

    while( M-- ) {

        fin >> x;
        fin >> y;

        ans = -Inf;
        aux = 0;
        Que( 1, 1, N, x, y );

        fout << ans << "\n";
    }

    fin.close();
    fout.close();

    return 0;
}