#include <cstdio>
#include <algorithm>
#define N 100005
using namespace std;

int n,m,i,v[N];
struct query
{
    long long stot;
    long long left;
    long long right;
    long long smax;
};
query arb[4*N];
long long pred,ans;

void build ( int node, int L, int R )
{
    if ( L == R )
    {
        arb[node].smax=arb[node].stot=arb[node].left=arb[node].right=v[L];
        return;
    }

    int mid=( L + R )/2;

    build ( 2*node, L, mid );
    build ( 2*node+1, mid+1, R );

    arb[node].stot = arb[2*node].stot + arb[2*node+1].stot;
    arb[node].left = max ( arb[ 2*node ].left, arb [2*node].stot+arb[2*node+1].left);
    arb[node].right= max (arb [ 2*node +1]. right, arb[2*node+1].stot+arb[2*node].right);
    arb[node].smax = max ( arb [2*node].smax, max(arb[2*node+1].smax, arb [2*node].right+ arb[2*node+1].left));
}

void query ( int node, int L, int R, int start, int finish )
{
    if ( start<=L && R<=finish )
    {
        ans = max(ans, max( arb[node].smax, arb[node].left+pred));
        pred= max (arb[node].right, pred+arb[node].stot);
        return;
    }

    int mid = (L+R)/2;

    if ( start <= mid ) query ( 2*node, L, mid, start, finish );
    if ( mid < finish ) query ( 2*node+1, mid+1, R, start, finish );


}


int main()
{

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

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

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

    build (1,1,n);

    for ( i=1; i<=m; i++)
    {
        int x,y;
        scanf ("%d%d", &x, &y);
        ans=pred=-1e16;
        query(1,1,n,x,y);
        printf ("%lld\n", ans);

    }


    return 0;
}