#include <fstream>
#include <algorithm>

#define INF 0x3f3f3f3f
#define NMAX (1<<18)
#define lf (nod<<1)
#define rt (lf+1)
#define mid ((left+right)>>1)


using namespace std;
ofstream out("sequencequery.out");

int V[NMAX] , A[NMAX << 1] , B[NMAX << 1 ] , C[NMAX << 1 ] , arb[ NMAX << 1 ];
int n , m;

int sum , sol;

void Read();
void build( int nod , int left , int right );
void query( int nod , int left , int right , int start , int finish);

int main()
{

    Read();
    return 0;

}

void Read()
{

    ifstream in("sequencequery.in");

    in >> n >> m;

    for( int i=1 ; i<=n ; i++)
        in >>V[i];

    build( 1 , 1 , n );


    for( int st , dr ; m ; --m )
    {

        in >> st >> dr ;

        sum = 0 , sol = -INF;

        query(1,1,n,st,dr);

        out << sol << '\n';

    }


}

void build( int nod , int left , int right )
{

    if( left == right )
    {
        A[nod] = B[nod] = C[nod] = arb[nod] = V[left];
        return;
    }

    //..

    build( lf , left , mid);
    build( rt , mid + 1 , right );

    A[nod] = max( A[lf] , arb[lf] + A[rt] );
    B[nod] = max( B[lf] + arb[rt] , B[rt] );
    C[nod] = max( max( C[lf] , C[rt] ) , B[lf] + A[rt] );

    arb[nod] = arb[lf] + arb[rt];

}

void query( int nod , int left , int right , int start , int finish )
{

    if( start <= left && right <= finish )
    {

        sum = max( sum , 0 );
        sol = max( sol , max( sum + A[nod] , C[nod] ));
        sum = max( sum + arb[nod] , B[nod] );
        return;
    }

    if( start <= mid )
        query( lf , left , mid , start , finish );

    if( finish > mid )
        query( rt , mid + 1 , right , start , finish );

}