#include<fstream>

using namespace std;

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

typedef long long i64;

const int nmax = 100000;
const i64 inf = (1LL << 62);

struct str{
    i64 x, all, y, sum;

    str() {}
    str( i64 _x, i64 _all, i64 _y, i64 _sum ) : x( _x ), all( _all ), y( _y ), sum( _sum ) {}
} ans, ai[ 4 * nmax ];

inline i64 max2( i64 a, i64 b ) {
    return ( a < b ? b : a );
}
str unify( str x, str y ) {
    str k;
    k.x = max2( x.x, x.sum + y.x );
    k.sum = x.sum + y.sum;
    k.y = max2( x.y + y.sum, y.y );
    k.all = max2( max2( x.all, y.all ), x.y + y.x );
    return k;
}
void update( int nod, int st, int dr, i64 val, int pos ) {
    if ( st == dr ) {
        ai[ nod ] = str( val, val, val, val );
        return ;
    }

    int mid = (st + dr) / 2;
    int p = (nod << 1), q = (nod << 1) + 1;

    if ( pos <= mid ) {
        update( p, st, mid, val, pos );
    } else {
        update( q, mid + 1, dr, val, pos );
    }

    ai[ nod ] = unify( ai[ p ], ai[ q ] );
 }
void query( int nod, int st, int dr, int x, int y ) {
    if ( x <= st && dr <= y ) {
        ans = unify( ans, ai[ nod ] );
        return ;
    }

    int mid = (st + dr) / 2;
    if ( x <= mid ) {
        query( (nod << 1), st, mid, x, y );
    }
    if ( y >= mid + 1 ) {
        query( (nod << 1) + 1, mid + 1, dr, x, y );
    }
}
int main() {
    int n, m, x, y, k;
    fin >> n >> m;
    for( int i = 1; i <= n; ++ i ) {
        fin >> k;
        update( 1, 1, n, (i64)k, i );
    }

    while ( m -- ) {
        fin >> x >> y;
        ans = str( -inf, -inf, -inf, -inf );
        query( 1, 1, n, x, y );
        fout << ans.all << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}