#include<stdio.h>
#define NMAX 100005
#define INF 2000000000000000LL
FILE *in,*out;

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

typedef struct arbint
{
    int max;
    int st;
    int dr;
    int s;
};
arbint v[4*NMAX];
int n,m,poz,i,val,start,finish;
long long rasp;


void Update(int,int,int);
void query(int,int,int);


int main()
{
    in=fopen("sequencequery.in","rt");
    out=fopen("sequencequery.out","wt");
    fscanf(in,"%d %d",&n,&m);
    for(i=1;i<=n;i++)
    {
        fscanf(in,"%d",&val);
        poz=i;
        Update(1,1,n);
    }
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d %d",&start,&finish);
        rasp=-INF;
        val=0;
        query(1,1,n);
        fprintf(out,"%lld\n",rasp);

    }

    return 0;
}

void Update(int nod,int left,int right)
{
    if(left==right)
    {
        v[nod].max=v[nod].st=v[nod].dr=v[nod].s=val;
        return;
    }
    int div=(left+right)>>1;
    if(poz<=div)
        Update(nod<<1,left,div);
    else
        Update((nod<<1)+1,div+1,right);
    int fiu=nod<<1;
    v[nod].max=maxim(v[fiu].dr+v[fiu+1].st , maxim(v[fiu].max,v[fiu+1].max));
    v[nod].s=v[fiu].s+v[fiu+1].s;
    v[nod].st=maxim(v[fiu].st , v[fiu].s + v[fiu+1].st);
    v[nod].dr=maxim(v[fiu+1].dr , v[fiu+1].s + v[fiu].dr);
}

void query(int nod,int left, int right)
{
    if(start<=left && finish>=right)
    {
        long long ret=v[nod].max;
        ret=maxim(ret , val+v[nod].st);
        val=maxim(val+v[nod].s , v[nod].dr);
        rasp=maxim(rasp,ret);
        return;
    }
    int div=(left+right)>>1;
    int fiu=nod<<1;
    if(start<=div)
        query(fiu,start,div);
    if(finish>div)
        query(fiu+1,div+1,right);

}