#include <cstdio>
#include <algorithm>
using namespace std;
#define Inf 0xfffffff
#define Max 1<<18
#define lf (2*n)
#define rt (2*n+1)

int n,x,y,a[Max],b[Max],s[Max],d[Max],rs,sub;

void update(int n,int l,int r)
{
    if(l==r)
    {
        a[n]=b[n]=s[n]=d[n]=y;
        return;
    }
        int m=(l+r)/2;
        if(x<=m)update(lf,l,m); else update(rt,m+1,r);
        a[n]=a[lf]+a[rt];
        b[n]=max(max(b[lf],b[rt]),d[lf]+s[rt]);
        s[n]=max(s[lf],a[lf]+s[rt]);
        d[n]=max(d[rt],a[rt]+d[lf]);
}

void query(int n,int l,int r)
{
    if(x<=l && r<=y)
    {
        //printf("%d %d\n",l,r);
        rs=max(rs,max(b[n],sub+s[n]));
        sub=max(sub+a[n],d[n]);
        return;
    }
        int m=(l+r)/2;
    if(x<=m)query(lf,l,m);
    if(y>m)query(rt,m+1,r);
}

int main()
{
    int m;
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&y);
            x=i;
            update(1,1,n);
        }
        //printf("%d\n",b[1]);
        while(m--)
        {
            scanf("%d %d",&x,&y);
            rs=-Inf;
            sub=0;
            query(1,1,n);
            printf("%d\n",rs);
        }
        //for(int i=1;i<=20;i++)printf("%d ",a[i]);

    return 0;
}