#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#define N 100010

using namespace std;

struct arbint {
    long long smax , stot , suf ,prec ;
};

long long v[ N ];
arbint t [ 4 * N ];

long long max( long long a , long long b ){

    if ( a < b ){
        a = b ;
    }

    return a ;
}



void build ( int nod , int l , int r ) {

    if ( l == r ){
        t [ nod ].smax = t [ nod ].prec = t [ nod ].suf =  v[ l ]   ;
        t [ nod ].stot = v [ l ];
        return ;
    }

    int left , right , mid  ;

    left = nod << 1;
    right = left + 1 ;
    mid = ( l + r ) / 2 ;

    build( left , l , mid );
    build( right , mid + 1  , r );

    t [ nod ].stot = t [ left ].stot + t [ right ].stot;

    t [ nod ].prec = max ( t [left].prec , t[ left ].stot + t[ right ].prec );

    t [ nod ].suf = max ( t[ right ].suf , t [ right ].stot + t[ left ].suf );

    t [ nod ].smax = max ( t [ right ].smax , max ( t [ left ].smax , t [ right ].prec + t [ left ].suf  ) ) ;

}


arbint query ( int nod , int l , int r , int a , int b ){

    if ( l == a && r == b ){
        return t[ nod ];
    }

    int left , right , mid  ;

    left = nod << 1;
    right = left + 1 ;
    mid = ( l + r ) / 2 ;

    if ( a > mid ){
        return query( right , mid + 1 , r , a , b  );
    }

    if ( b <= mid ){
        return query( left , l , mid , a , b );
    }

    arbint lv , rv , sol ;

    lv = query( left , l , mid , a , mid );
    rv = query( right , mid +1 , r , mid + 1 , b );

    sol.stot = lv.stot + rv.stot;

    sol.prec = max ( lv.prec , lv.stot + rv.prec );

    sol.suf = max ( rv.suf , rv.stot + lv.suf );

    sol.smax = max ( rv.smax , max ( lv.smax , rv.prec + lv.suf  ) ) ;

    return sol ;
}



int main(){
    int n , i ;
    int q , a , b;

    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);

    scanf("%d%d",&n , &q );

    for ( i = 1 ; i <= n ; i++ ){
        scanf("%lld",&v[ i ] );
    }

    build ( 1 , 1 , n  );

    for ( i = 0 ; i < q ; i ++ ){

        scanf("%d%d",&a , &b );

        printf("%lld\n", query ( 1 , 1 , n  , a , b ).smax  );

    }


    return 0;
}