#include <stdio.h>
#include <algorithm>
#define NMax 100010
using namespace std;

typedef long long ll;
const char IN[]="sequencequery.in",OUT[]="sequencequery.out";
const ll INF= 100000000000000LL;

int N,M;
int a[NMax];
ll A[2*NMax] , B[2*NMax] , C[2*NMax] , Sum[2*NMax] , ret , S;

void make(int poz,int st,int dr)
{
    if (st==dr){
        A[poz]=B[poz]=C[poz]=Sum[poz]=a[st];
        return;
    }
    int m=(st+dr)>>1;

    make( 2*poz  , st , m );
    make( 2*poz+1, m+1, dr);

    A[poz]= max( A[2*poz]  , Sum[2*poz]+A[2*poz+1] );
    B[poz]= max( B[2*poz+1], B[2*poz]+Sum[2*poz+1] );
    C[poz]= max( max ( C[2*poz] , C[2*poz+1] ) , B[2*poz]+A[2*poz+1]);

    Sum[poz]= Sum[2*poz]+Sum[2*poz+1];
}

void Query(int poz,int st,int dr,int x,int y)
{
    if ( x<=st && dr<=y )
    {
        ret= max ( ret , max( S+A[poz] , C[poz] ));
        S= max( S+Sum[poz] , B[poz] );
        return;
    }
    int m=(st+dr)>>1;

    if ( x<=m ) Query(2*poz  , st , m , x , y );
    if ( y >m ) Query(2*poz+1, m+1, dr, x , y );
}

int main()
{
    int i,x,y;
    freopen(IN,"r",stdin);
    scanf("%d%d",&N,&M);
    for (i=0;i<N;++i) scanf("%d",a+i);

    make(1,0,N-1);

    freopen(OUT,"w",stdout);
    while (M--)
    {
        scanf("%d%d",&x,&y);--x;--y;

        ret=-INF;S=0;
        Query(1,0,N-1,x,y);
        printf("%lld\n",ret);
    }
    fclose(stdout);
    fclose(stdin);

    return 0;
}