#include<fstream>
using namespace std;
int n,m,i,j,x,A,B,s,rez,v[100001];
struct arbore
{
    int sum,left,right,max1;
};
arbore a[501001];
void creare(int nod, int st,int dr)
{
    int mij;
    if(st==dr)
    {
        a[nod].sum=a[nod].left=a[nod].right=a[nod].max1=v[st];
        return;
    }
        mij=(st+dr)/2;
       // if(poz<=mij)
        creare(2*nod,st,mij);
       // else
        creare(2*nod+1,mij+1,dr);
        a[nod].sum=a[2*nod].sum+a[2*nod+1].sum;
        a[nod].left=max(a[2*nod].left,a[2*nod].sum+a[2*nod+1].left);
        a[nod].right=max(a[2*nod].right+a[2*nod+1].sum,a[2*nod+1].right);
        a[nod].max1=max(max(a[2*nod].max1,a[2*nod+1].max1),a[2*nod+1].left+a[2*nod].right);

}
void det(int nod,int st, int dr)
{
    int mij;
    if(A<=st&&dr<=B)
    {
        if(s<0)
        s=0;
        rez=max(rez,max(a[nod].max1,a[nod].left+s));
        s=max(a[nod].sum+s,a[nod].right);
        return;
    }
        mij=(st+dr)/2;
     if(A<=mij)
        det(2*nod,st,mij);
     if(mij<B)
        det(2*nod+1,mij+1,dr);

}
int main()
{
    ifstream f("sequencequery.in");
    ofstream g("sequencequery.out");
    f>>n>>m;
    for(i=1;i<=n;++i)
        f>>v[i];
        creare(1,1,n);
    for(i=1;i<=m;++i)
    {
        f>>A>>B;
        rez=-1000000000LL;
        s=0LL;
        det(1,1,n);
        g<<rez<<'\n';
    }
}