#include<stdio.h>
#include<algorithm>
using namespace std;
struct T
{
    long long sum,pref,suf,ans;
};
int N,Q;
T sol,aint[600005];
void recompute(T &A,T B,T C)
{
    A.sum=B.sum+C.sum;
    A.pref=max(B.pref,B.sum+C.pref);
    A.suf=max(C.suf,B.suf+C.sum);
    A.ans=max(B.suf+C.pref,max(B.ans,C.ans));
}
inline void update(int nod,int st,int dr,int pos,int value)
{
    if(st==dr)
    {
        aint[nod].sum=value;
        aint[nod].pref=value;
        aint[nod].suf=value;
        aint[nod].ans=value;
        return;
    }
    int med=(st+dr)/2;
    if(pos <= med)
        update(2*nod,st,med,pos,value);
    else
        update(2*nod+1,med+1,dr,pos,value);
    recompute(aint[nod],aint[2*nod],aint[2*nod+1]);
}
inline void query(int nod,int st,int dr,int x,int y)
{
    if(dr<x || y<st)
        return;
    if(x<=st && dr<=y)
    {
        recompute(sol,sol,aint[nod]);
        return;
    }
    int med=(st+dr)/2;
    if(med>=x)
        query(2*nod,st,med,x,y);
    if(med+1<=y)
        query(2*nod+1,med+1,dr,x,y);
}
int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    int x,y;
    scanf("%d%d",&N,&Q);
    for(int i=1;i<=N;++i)
    {
        scanf("%d",&x);
        update(1,1,N,i,x);
    }
    for(int i=1;i<=Q;++i)
    {
        scanf("%d%d",&x,&y);
        sol.sum=sol.suf=sol.pref=0;
        sol.ans=-1000000000;
        query(1,1,N,x,y);
        printf("%lld\n",sol.ans);
    }
    return 0;
}