#include <cstdio>
#define NMAX 400001
#define LMAX 100001
int a[NMAX],b[NMAX],c[NMAX],sum[NMAX];
int n,m;
int nr[100001];
int ans=0,su=0;
int max(int a,int b)
{
    if(a<b) return b;
    return a;
}
void putsum(int s,int e,int pos,int nod)
{
     if(s==e) sum[nod]=nr[pos];
     else
     {
         int mij=(s+e)/2;
         if(pos<=mij) putsum(s,mij,pos,2*nod);
         else putsum(mij+1,e,pos,2*nod+1);
         sum[nod]=sum[2*nod]+sum[2*nod+1];
     }
}
void update(int s,int e,int pos,int nod)
{
     if(s==e)
     {
             a[nod]=nr[pos];
             b[nod]=nr[pos];
             c[nod]=nr[pos];
     }
     else
     {
         int mij=(s+e)/2;
         if(pos<=mij) update(s,mij,pos,2*nod);
         else update(mij+1,e,pos,2*nod+1);
         a[nod]=max(a[2*nod],sum[2*nod]+a[2*nod+1]);
         b[nod]=max(b[2*nod+1],sum[2*nod+1]+b[2*nod]);
         c[nod]=max(max(c[2*nod],c[2*nod+1]),b[2*nod]+a[2*nod+1]);
     }
}
void query(int s,int e,int p1,int p2,int nod)
{
     if(p1<=s&&e<=p2)
     {
                     ans=max(ans,max(su+a[nod],c[nod]));
                     su=max(su+sum[nod],b[nod]);
     }
     else
     {
         int mij=(s+e)/2;
         if(p1<=mij) query(s,mij,p1,p2,2*nod);
         if(p2>mij) query(mij+1,e,p1,p2,2*nod+1);
     }
}
int main()
{
    freopen ("sequencequery.in","r",stdin);
    freopen ("sequencequery.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
            scanf("%d",&nr[i]);
            putsum(1,n,i,1);
    }
    for(int i=1;i<=n;i++)  update(1,n,i,1);
    int p1,p2;
    for(int i=1;i<=m;i++)
    {
            ans=-100000000,su=0;
            scanf("%d%d",&p1,&p2);
            query(1,n,p1,p2,1);  
            printf("%d\n",ans);
    }
}