#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

FILE *fin, *fout;

int v[100000];
long long aint[1<<18][4];
int x, y;
long long sumamax, sc;

int read() {
    int nr, d = 1;
    char ch;
    ch = fgetc( fin );
    while ( isdigit( ch ) == 0 && ch != '-' )
        ch = fgetc( fin );
    if ( ch == '-' ) {
        d = -1;
        ch = fgetc( fin );
    }
    nr = 0;
    while ( isdigit( ch ) ) {
        nr = nr * 10 + ( ch - '0' );
        ch = fgetc( fin );
    }
    return nr * d;
}

long long max( long long a, long long b ) {
    if ( a > b )
        return a;
    return b;
}

void arboreInterval( int st, int dr, int p ) {
    if ( st == dr ) {
        aint[p][0] = v[st];
        aint[p][1] = v[st];
        aint[p][2] = v[st];
        aint[p][3] = v[st];
    }
    else {
        arboreInterval( st, ( st + dr ) / 2, 2 * p );
        arboreInterval( ( st + dr ) / 2 + 1, dr, 2 * p + 1 );
        aint[p][0] = aint[2*p][0] + aint[2*p+1][0];
        aint[p][1] = max( aint[2*p][1], aint[2*p][0] + aint[2*p+1][1] );
        aint[p][2] = max( aint[2*p+1][2], aint[2*p+1][0] + aint[2*p][2] );
        aint[p][3] = max( max( aint[2*p][3] , aint[2*p+1][3] ), aint[2*p][2] + aint[2*p+1][1] );
    }
}

void query( int st, int dr, int p ) {
    if ( x <= st && dr <= y ) {
        sumamax = max( sumamax, sc + aint[p][1] );
        sc = max( sc + aint[p][0], aint[p][2] );
        sumamax = max( max( sumamax, aint[p][3] ) , sc );
    }
    else {
      if ( x <= ( st + dr ) / 2 )
          query( st, ( st + dr ) / 2, 2 * p );
      if ( ( st + dr ) / 2 + 1 <= y )
          query( ( st + dr ) / 2 + 1, dr, 2 * p + 1 );
    }
}

int main() {
    int n, m, i;
    fin = fopen( "sequencequery.in", "r" );
    fout = fopen( "sequencequery.out", "w" );
    n = read();
    m = read();
    for ( i = 0; i < n; i++ )
        v[i] = read();
    arboreInterval( 0, n - 1, 1 );
    for ( i = 0; i < m; i++ ) {
        x = read();
        y = read();
        x--;
        y--;
        sumamax = -100001;
        sc = 0;
        query( 0, n - 1, 1 );
        fprintf( fout, "%lld\n", sumamax );
    }
    fclose( fin );
    fclose( fout );
    return 0;
}