using namespace std;
#include<iostream>
#include<fstream>
#define nmax 300005
#define common int mij=(l+r)/2,L=2*n,R=L+1
int m[nmax],ms[nmax],md[nmax],tot[nmax];
int a[100005],N,M,s,ans;

ofstream fout("sequencequery.out");
void query(int n,int ql,int qr,int l,int r)
{
    if(ql<=l && r<=qr)
    {
        ans=max(ans,max(s+ms[n],m[n]));
        s=max(s+tot[n],md[n]);
      return;
    }

    common;

    if(ql<=mij)
        query(L,ql,qr,l,mij);
    if(qr>=mij+1)
        query(R,ql,qr,mij+1,r);


}

void build(int n,int l,int r)
{
    if(l>=r) {m[n]=ms[n]=md[n]=tot[n]=a[l]; return;}

    common;

    build(L,l,mij);
    build(R,mij+1,r);

    tot[n]=tot[L]+tot[R];
    ms[n]=max(ms[L],tot[L]+ms[R]);
    md[n]=max(md[R],tot[R]+md[L]);
    m[n]=max(max(max(ms[n],md[n]),max(m[L],m[R])),md[L]+ms[R]);

}

void cit()
{int i,x,y;
    ifstream fin("sequencequery.in");
    fin>>N>>M;

    for(i=1;i<=N;i++)
    {
        fin>>a[i];

    }
    build(1,1,N);

    for(i=1;i<=M;i++)
    {

        fin>>x>>y;
        s=ans=-0x3f3f3f3f;
        query(1,x,y,1,N);
        fout<<ans<<"\n";
    }

}

int main()
{
    cit();
    fout.close();
    return 0;
}