#include<cstdio>

const int nmax=4*1e5+66;

long long sp[nmax],stmax[nmax],drmax[nmax],smax[nmax];
int n;

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

inline void update(int nod,int st,int dr,int pos,int val)
{
     if (st==dr){
        sp[nod]=1LL*val;
        stmax[nod]=1LL*val;
        drmax[nod]=1LL*val;
        smax[nod]=1LL*val;
        return;
    }
    int mij=(st + dr) / 2;
    if (pos<=mij){
        update (nod*2, st, mij, pos,val);
    }
    else{
        update (nod*2+1, mij+1, dr, pos,val);
    }
    sp[nod]=sp[nod*2]+sp[nod*2+1];
    stmax[nod]=max(stmax[nod*2], sp[nod*2] + stmax[nod*2+1]);
    drmax[nod]=max(drmax[nod*2 + 1], drmax[nod*2] + sp[nod*2+1]);
    smax[nod]=max(max(max(max(max(stmax[nod], drmax[nod]), drmax[nod*2] + stmax[nod*2 + 1]),sp[nod]),smax[nod*2]), smax[nod*2+1]);}

inline void query(int nod,int st,int dr,int l,int r,long long &sum,long long &summax)
{
    if (l<=st && r>=dr){
        if (sum < 0) {
            sum = 0 ;
        }
        summax = max (max (summax, sum + stmax [nod]), smax [nod]) ;
        sum = max(sum + sp [nod], drmax [nod]) ;
        return ;
    }
    int med=(st+dr) >>1;
    if (l<=med){
        query (nod*2, st, med, l, r, sum, summax);
    }
    if (r>med) {
        query(nod * 2 + 1, med + 1, dr, l, r, sum, summax);
    }
}

int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    int i,m,x,a,b;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)
    {
        scanf("%d",&x);
        update(1,1,n,i,x);
    }
    long long rez,sum;
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&a,&b);
        rez=-100000;
        sum=0;
        query(1,1,n,a,b,sum,rez);
        printf("%d\n",rez);
    }
}