#include<cstdio>
#define NMAX 200005
#define max(a,b)(a>b?a:b)
#define INF -10000000005
using namespace std;
int a[NMAX*4],b[NMAX*4],c[NMAX*4],v[NMAX/2],sum[NMAX*4],Max[NMAX*4];
int n,x,y,i,m,sol,S,ok;
long long M;
void build(int nod,int st,int dr)
{
    if (st==dr)
    {
        a[nod]=b[nod]=c[nod]=max(v[st],0);
        sum[nod]=v[st];
        Max[nod]=v[st];
    }
    else
    {

    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);

    a[nod]= max (a[nod*2], a[nod*2+1]+sum[nod*2]);
    b[nod]= max (b[nod*2+1], b[nod*2]+sum[nod*2+1]);
    c[nod]= max (max(c[nod*2], c[nod*2+1]), b[nod*2]+a[nod*2+1]);
    sum[nod]=sum[nod*2]+sum[nod*2+1];
    Max[nod]=max(Max[nod*2],Max[nod*2+1]);

    }
}
void calculeaza(int nod,int st,int dr)
{
    if (x<=st && dr<=y)
    {
        if (S<0) S=0;
        if (sol<max(S+a[nod],c[nod])) {sol=max(S+a[nod],c[nod]);ok=1;}
        S=max(S+sum[nod],b[nod]);
        if (Max[nod]>M) M=Max[nod];
    }
    else
    {
        int mij=(st+dr)/2;
        if (x<=mij) calculeaza(nod*2,st,mij);
        if (y>mij) calculeaza(nod*2+1,mij+1,dr);
    }
}
int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;++i)
    {
        scanf("%d",&v[i]);
    }
    build(1,1,n);
     for (i=1;i<=m;++i)
    {
        scanf("%d%d",&x,&y);
        sol=0;S=0;M=INF;ok=0;
        calculeaza(1,1,n);
        if (ok==1) printf("%d\n",sol);
            else printf("%d\n",M);
    }
    return 0;
}