#include <cstdio>
#include <algorithm>

using namespace std;

#define IN_FILE "sequencequery.in"
#define OUT_FILE "sequencequery.out"
#define MAX_NODE 400005

struct aint {
    long long s, b, st, dr;
} aint[ MAX_NODE ];
long long best, s;
void update( int nod, int st, int dr, int poz, int val ) {
    if( st == dr ) {
        aint[ nod ].s = aint[ nod ].b = aint[ nod ].st = aint[ nod ].dr = val;
        return;
    }
    int mid = st + ( ( dr - st ) >> 1 );
    if( poz <= mid )
        update( nod << 1, st, mid, poz, val );
    else
        update( ( nod << 1 ) + 1, mid + 1, dr, poz, val );
    aint[ nod ].s = aint[ ( nod << 1 ) ].s + aint[ ( nod << 1 ) + 1 ].s;
    aint[ nod ].b = max( aint[ ( nod << 1 ) ].dr + aint[ ( nod << 1 ) + 1 ].st, max( aint[ ( nod << 1 ) ].b, aint[ ( nod << 1 ) + 1 ].b ) );
    aint[ nod ].st = max( aint[ ( nod << 1 ) ].st, aint[ ( nod << 1 ) ].s + aint[ ( nod << 1 ) + 1 ].st );
    aint[ nod ].dr = max( aint[ ( nod << 1 ) + 1 ].dr, aint[ ( nod << 1 ) + 1 ].s + aint[ ( nod << 1 ) ].dr );
}
void query( int nod, int st, int dr, int x, int y ) {
    if( x <= st && y >= dr ) {
        best = max( best, max( aint[ nod ].b, s + aint[ nod ].st ) );
        s = max( s + aint[ nod ].s, aint[ nod ].dr );
        return;
    }
    int mid = st + ( ( dr - st ) >> 1 );
    if( x <= mid )
        query( nod << 1, st, mid, x, y );
    if( y > mid )
        query( ( nod << 1 ) + 1, mid + 1, dr, x, y );
}
int main( ) {
    FILE *f, *g;
    int N, Q, i, x, y;

    f = fopen( IN_FILE, "r" );
    fscanf( f, "%d%d", &N, &Q );
    for( i = 1; i <= N; ++i ) {
        fscanf( f, "%d", &x );
        update( 1, 1, N, i, x );
    }
    g = fopen( OUT_FILE, "w" );
    while( Q-- ) {
        fscanf( f, "%d%d", &x, &y );
        best = -( 1LL << 60 );
        s = 0;
        query( 1, 1, N, x, y );
        fprintf( g, "%lld\n", best );
    }
    fclose( f );
    fclose( g );
    return 0;
}