#include <stdio.h>
    
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")

const long long INF = 999999999999999;

static inline long long min( long long a, long long b ) {
    return ( a <= b ? a : b );
}
 
static inline long long max( long long a, long long b ) {
    return ( a >= b ? a : b );
}
 
struct Andrei {
    long long left, maxx, suma, right;
};

Andrei tree[ 800000 ];
int v[ 100001 ];

    
void update( int nod, int st, int dr, int poz, int val ){
    if( st == dr )
        tree[ nod ] = { val, val, val, val };
    else {
        int med = ( st + dr ) >> 1;
        if( poz <= med )
            update( nod * 2, st, med, poz, val );
        else update( nod * 2 + 1, med + 1, dr, poz, val );
     
        tree[ nod ].suma = tree[ nod * 2 ].suma + tree[ nod * 2 + 1 ].suma;
        tree[ nod ].maxx = max( tree[ nod * 2 ].right + tree[ nod * 2 + 1 ].left, max( tree[ nod * 2 ].maxx, tree[ nod * 2 + 1 ].maxx ) );
        tree[ nod ].left = max( tree[ nod * 2 ].left, tree[ nod * 2 ].suma + tree[ nod * 2 + 1 ].left );
        tree[ nod ].right = max( tree[ nod * 2 + 1 ].right, tree[ nod * 2 + 1 ].suma + tree[ nod * 2 ].right );
    }
}
 
void query( int nod, int st, int dr, int a, int b, long long &suma, long long &s ) {
    if( a <= st && dr <= b ) {
        s = max( s, max( tree[ nod ].maxx, suma + tree[ nod ].left ) );
        suma = max( suma + tree[ nod ].suma, tree[ nod ].right );
    } else {
        int med = ( st + dr ) >> 1;
        if( a <= med )
            query( nod * 2, st, med, a, b, suma, s );
        if( med < b )
            query( nod * 2 + 1, med + 1, dr, a, b, suma, s );
    }
}

int main()
{
    FILE *fin = fopen( "sequencequery.in", "r" );

    int n, m;
    fscanf( fin, "%d%d", &n, &m );
    for( int i = 1; i <= n; i++ ) {
        //v[ i ] = readInt();
        fscanf( fin, "%d", &v[ i ] );
        update( 1, 1, n, i, v[ i ] );
    }

    int a, b;
    FILE *fout = fopen( "sequencequery.out", "w" );
    for( int i = 1; i <= m; i++ ) {
        //a = readInt();
        //b = readInt();
        fscanf( fin, "%d%d", &a, &b );
        long long s = -INF;
        long long rez = -INF;

        query( 1, 1, n, a, b, rez, s );
        fprintf( fout, "%lld\n", s );
    }
    return 0;
}