#include <stdio.h>

struct sequence
{
    int all,left,right,best;
};

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

sequence v[263000];

sequence query(int l,int r,int s,int d,int node)
{
    if ((s>r)||(d<l)) return v[0];
    if ((l<=s)&&(r>=d)) return v[node];
    sequence a,b,c;
    a=query(l,r,s,(s+d)/2,2*node);
    b=query(l,r,(s+d)/2+1,d,2*node+1);
    c.all=a.all+b.all;
    c.left=max(a.all+b.left,a.left);
    c.right=max(a.right+b.all,b.right);
    c.best=max(a.right+b.left,max(a.best,b.best));
    return c;
}

int main()
{
    int n,m,d,i,x,y;
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (d=1;d<n;d<<=1);
    v[0].all=-100000;v[0].best=-100000;v[0].left=-100000;v[0].right=-100000;
    for (i=d;i<d+n;++i)
    {
        scanf("%d",&v[i].all);
        v[i].left=v[i].all;
        v[i].right=v[i].all;
        v[i].best=v[i].all;
    }
    for (i=d-1;i>0;--i)
    {
        v[i].all=v[2*i].all+v[2*i+1].all;
        v[i].left=max(v[2*i].all+v[2*i+1].left,v[2*i].left);
        v[i].right=max(v[2*i].right+v[2*i+1].all,v[2*i+1].right);
        v[i].best=max(v[2*i].right+v[2*i+1].left,max(v[2*i].best,v[2*i+1].best));
    }
    for (i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",query(x,y,1,d,1).best);
    }
    return 0;
}