#include<fstream>
#include<algorithm>
using namespace std;

long long i,j,n,m,x,a[100001],y,rez,s=0;
struct arbint
{
    long long sum,st,dr,maxim;
};
arbint arb[3000001];
void creare(int nod,int st,int dr)
{
    int mij;
    if(st==dr)
    {
    arb[nod].sum=arb[nod].st=arb[nod].dr=arb[nod].maxim=a[st];
    return ;
    }
    mij=(st+dr)/2;
        creare(nod*2,st,mij);
        creare(nod*2+1,mij+1,dr);
        arb[nod].sum=arb[nod*2].sum+arb[nod*2+1].sum; // suma elem din intervalul curent
        arb[nod].st=max(arb[nod*2].st,arb[nod*2].sum+arb[nod*2+1].st); //val subsecv de suma max a elem de la inceputul inervalului
        arb[nod].dr=max(arb[nod*2+1].dr,arb[nod*2+1].sum+arb[nod*2].dr);//val subsecv de suma max a elem de la sfarsitul intervalului
        arb[nod].maxim=max(max(arb[nod*2].maxim,arb[nod*2+1].maxim),arb[nod*2+1].st+arb[nod*2].dr); //val subsecv de suma max a elem situate oriunde in interval

}
void det(int nod,int st,int dr,int a,int b)
{
    int mij;
    if(a<=st&&b>=dr)
    {
        if(s<0)
        s=0;
        rez=max(rez,max(arb[nod].maxim,arb[nod].st+s));
        s=max(arb[nod].sum+s,arb[nod].dr);
        return ;
    }
    mij=(st+dr)/2;
    if(a<=mij)
    det(nod*2,st,mij,a,b);
    if(mij<b)
    det(nod*2+1,mij+1,dr,a,b);
}
int main()
{
    ifstream f("sequencequery.in");
    ofstream g("sequencequery.out");
    f>>n>>m;
    for(i=1;i<=n;++i)
        f>>a[i];
        creare(1,1,n);
        for(i=1;i<=m;++i)
        {
            f>>x>>y;
            rez=-1<<20;
            s=0;
            det(1,1,n,x,y);
            g<<rez<<"\n";
        }
    return 0;
}