#include <fstream>

const char IN [ ] = "sequencequery.in" ;
const char OUT [ ] = "sequencequery.out" ;
const int MAX = 200000 << 2 ;
const int MAXI = 200014 ;

using namespace std;

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

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

struct arbore {
    long long sp ;
    long long smax ;
    long long stmax ;
    long long drmax ;
};

arbore q [ MAX ] ;

int v [ MAXI ] , poz , x , poz1 , poz2;

#define left_son (n << 1)
#define right_son left_son + 1

void build ( int n , int st , int dr )
{
    if ( st == dr )
    {
        q [ n ].smax = q [ n ].stmax = q [ n ].drmax = v [ st ];
        q [ n ].sp = v [ st ] ;
    }
    else {
        int mij = ( st + dr ) >> 1 ;
        build ( left_son , st , mij ) ;
        build ( right_son , mij + 1 , dr ) ;
        q [ n ].smax = MAXX ( MAXX (q [ left_son ].smax , q[ right_son ].smax) ,q[ left_son ].drmax + q[ right_son ].stmax ) ;
        q [ n ].stmax = MAXX ( q [ left_son ].stmax , q[ left_son ].sp + q[ right_son ].stmax );
        q [ n ].drmax = MAXX ( q [ right_son ].drmax , q[ right_son ].sp + q[ left_son ].drmax );
        q [ n ].sp = q [ right_son ].sp + q [ left_son ].sp ;
    }
}

void updt ( int n , int st , int dr )
{
    if ( st == dr )
    {
        q [ n ].smax = q [ n ].stmax = q [ n ].drmax = max ( x , 0 );
        q [ n ].sp = x ;
    }
    else {
        int mij = ( st + dr ) >> 1 ;
        if (poz <= mij) updt( left_son , st , mij ) ;
            else updt( right_son , mij + 1  , dr ) ;
        q [ n ].smax = MAXX ( MAXX (q [ left_son ].smax , q[ right_son ].smax) ,q[ left_son ].drmax + q[ right_son ].stmax ) ;
        q [ n ].stmax = MAXX ( q [ left_son ].stmax , q[ left_son ].sp + q[ right_son ].stmax );
        q [ n ].drmax = MAXX ( q [ right_son ].drmax , q[ right_son ].sp + q[ left_son ].drmax );
        q [ n ].sp = q [ right_son ].sp + q [ left_son ].sp ;
    }
}
long long SOL , S ;
void query ( int n , int st , int dr )
{
    if ( poz1 <= st and dr <= poz2 )
    {
        //if ( S < 0 ) S = 0 ;
        SOL = MAXX ( SOL , MAXX ( S + q [ n ].stmax , q [ n ].smax ) ) ;
        S = MAXX ( S + q [ n ].sp , q [ n ].drmax ) ;
    }
    else {
        int mij = ( st + dr ) >> 1 ;
        if ( poz1 <= mij ) query ( left_son , st , mij ) ;
        if ( poz2 > mij ) query ( right_son , mij + 1 , dr ) ;
    }
}
int main( )
{
    int n , m ;
    fin >> n >> m ;
    for ( int i = 1 ; i <= n ;++ i )
        fin >> v [ i ] ;
    build ( 1 , 1 , n ) ;
    while ( m -- )
    {
        //int qu ;
        //fin >> qu;
        //if ( qu == 0 ){
        //    fin >> poz >> x ;
        //    ++ poz ;
        //    updt ( 1 ,1 ,n );
        //}
       // else {
        SOL = S = - (1 << 30) ;
        fin >> poz1 >> poz2;
            //++ poz1 ;
            //++ poz2 ;
        query( 1 , 1 , n ) ;
        fout << SOL << '\n' ;
       // }
    }
    return 0;
}