#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;
};

    
FILE *fin;
 
int poz, valBuff;
static char buff[ ( 1 << 7 ) ];
static inline char nextChar() {
    if( poz == valBuff ) {
        fread( buff, 1, valBuff, fin );
        poz = 0;
    }
 
    return buff[ poz++ ];
}
 
static bool f[ 100 ];
static inline int readInt() {
    int rez = 0, semn = 1;
    int ch;
 
    while( !f[ ch = nextChar() ] );
    if( ch == '-' ) {
        ch = nextChar();
        semn = -1;
    }
    do
        rez = rez * 10 + ch - '0';
    while( f[ ch = nextChar() ] );
 
    return rez * semn;
}
 
//////////////////////////////////////////////////////////////////////////////////////////////

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

    
void makeTree( int nod, int left, int right ){
    if( left == right )
        tree[ nod ] = { v[ left ], v[ left ], v[ left ], v[ left ] };
    else {
        const int med = ( left + right ) >> 1;
        const int R = nod + 2 * ( med - left + 1 );
        const int L = nod + 1;
        
        makeTree( L, left, med );
        makeTree( R, med + 1 , right );
     
        tree[ nod ].suma = tree[ L ].suma + tree[ R ].suma;
        tree[ nod ].maxx = max( tree[ L ].right + tree[ R ].left, max( tree[ L ].maxx, tree[ R ].maxx ) );
        tree[ nod ].left = max( tree[ L ].left, tree[ L ].suma + tree[ R ].left );
        tree[ nod ].right = max( tree[ R ].right, tree[ R ].suma + tree[ L ].right );
    }
}
 
void query( int nod, int left, int right, int a, int b, long long &suma, long long &s ) {
    if( a <= left && right <= b ) {
        s = max( s, max( tree[ nod ].maxx, suma + tree[ nod ].left ) );
        suma = max( suma + tree[ nod ].suma, tree[ nod ].right );
    } else {
        const int med = ( left + right ) >> 1;
        const int R = nod + 2 * ( med - left + 1 );
        const int L = nod + 1;

        if( a <= med )
            query( L, left, med, a, b, suma, s );
        if( med < b )
            query( R, med + 1, right, a, b, suma, s );
    }
}

int main()
{
    f[ '0' ] = f[ '1' ] = f[ '2' ] = f[ '3' ] = f[ '4' ] = 1;
    f[ '6' ] = f[ '7' ] = f[ '8' ] = f[ '9' ] = f[ '5' ] = f[ '-' ] = 1;
    valBuff = sizeof( buff );
 
    fin = fopen( "sequencequery.in", "r" );
    fread( buff, 1, valBuff, fin );

    int n, m;
    n = readInt();
    m = readInt();
    for( int i = 1; i <= n; i++ )
        v[ i ] = readInt();

    makeTree( 1, 1, n );

    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;
}