#include <cstdio>
#include <algorithm>
using namespace std;
struct arb{
long long tot,st,dr,best;
}a[800005];
long long ans,p;
int in,sf,poz,val;
void update(int nod,int left,int right){
if(left==right){
    a[nod].tot=0LL+val;
    a[nod].st=0LL+val;
    a[nod].dr=0LL+val;
    a[nod].best=0LL+val;
    return;
}
int mij=(left+right)/2;
if(poz<=mij)update(nod*2,left,mij);
else update(nod*2+1,mij+1,right);
a[nod].tot=0LL+a[nod*2].tot+a[nod*2+1].tot;
a[nod].st=0LL+max(a[nod*2].tot+a[nod*2+1].st,a[nod*2].st);
a[nod].dr=0LL+max(a[nod*2+1].dr,a[nod*2+1].tot+a[nod*2].dr);
a[nod].best=0LL+max(max(a[nod*2].best,a[nod*2+1].best),a[nod*2+1].st+a[nod*2].dr);
}
void query(int nod,int left,int right){
if(in<=left && right<=sf){
    ans=0LL+max(max(ans,a[nod].best),p+a[nod].st);
    p=0LL+max(a[nod].tot+p,a[nod].dr);
    return;
}
int mij=(left+right)/2;
if(in<=mij)query(nod*2,left,mij);
if(mij<sf)query(nod*2+1,mij+1,right);
}
int i,j,n,m,x;
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",&x);
        poz=i;
        val=x;
        update(1,1,n);
    }
    for(i=1;i<=m;i++){
        scanf("%d %d",&in,&sf);
        ans=-10000000000000000;
        p=0;
        query(1,1,n);
        printf("%lld\n",ans);
    }

    return 0;
}