#include <cstdio>
#include <cstring>
#define inf 1000000000

using namespace std;

int s[300010],v1[300010],v2[300010],v3[300010],n,m,i,x,l,r,sum,maxim,poz;

int max(int a,int b)
{
    if(a>b) return a;
    else return b;
}

void schimba(int nod,int st,int dr)
{
    if(st==dr)
    {
        s[nod]=x;
        v1[nod]=x;
        v2[nod]=x;
        v3[nod]=x;
        return;
    }
    int mid=(st+dr)/2;
    if(poz<=mid) schimba(nod*2,st,mid);
    else schimba(nod*2+1,mid+1,dr);
    s[nod]=s[nod*2]+s[nod*2+1];
    v1[nod]=max(v1[nod*2],s[nod*2]+v1[nod*2+1]);
    v2[nod]=max(v2[nod*2+1],s[nod*2+1]+v2[nod*2]);
    v3[nod]=max(max(v3[nod*2],v3[nod*2+1]),v2[nod*2]+v1[nod*2+1]);
}

void raspunde(int nod,int st,int dr)
{
    if(l<=st && dr<=r)
    {
        maxim=max(maxim,max(v3[nod],sum+v1[nod]));
        sum=max(sum+s[nod],v2[nod]);
        return;
    }
    int mid=(st+dr)/2;
    if(l<=mid) raspunde(nod*2,st,mid);
    if(r>mid) raspunde(nod*2+1,mid+1,dr);
}

int main()
{
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    scanf("%d%d",&n,&m);
    memset(v1,-inf,sizeof(v1));
    memset(v2,-inf,sizeof(v2));
    memset(v3,-inf,sizeof(v3));
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        poz=i;
        schimba(1,1,n);
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        maxim=-inf;
        sum=0;
        raspunde(1,1,n);
        printf("%d\n",maxim);
    }
    fclose(stdin);fclose(stdout);
    return 0;
}