#include<bits/stdc++.h>
#define NMAX 100005
using namespace std;

ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

struct arb{
    int prefix,sufix,tot,ans;
}Arb[NMAX];
int val,poz,n,start,finish;

void Up(int node,int st,int dr)
{
    if(st==dr)
    {
        Arb[node].prefix=val;
        Arb[node].sufix=val;
        Arb[node].tot=val;
        Arb[node].ans=val;
        return;
    }

    int mij=(dr+st)/2;
    if(poz<=mij)
        Up(node*2,st,mij);
    else
        Up(node*2+1,mij+1,dr);
    Arb[node].prefix=max(Arb[node*2].prefix,Arb[node*2].tot+Arb[node*2+1].prefix);
    Arb[node].sufix=max(Arb[node*2+1].sufix,Arb[node*2+1].tot+Arb[node*2].sufix);
    Arb[node].tot=Arb[node*2].tot+Arb[node*2+1].tot;
    Arb[node].ans=max(Arb[node*2].ans,max(Arb[node*2+1].ans,Arb[node*2].sufix+Arb[node*2+1].prefix));

}

arb Cauta(int node,int st,int dr)
{
    if(start>dr || finish<st)
    {
        arb r;
        r.ans=-999999;
        r.prefix=-999999;
        r.sufix=-9999999;
        r.tot=-999999;
        return r;
    }

    if(start<=st && dr<=finish)
    {
        return Arb[node];

    }
    int mij=(dr+st)/2;
    arb a1;
    arb a2;
    a1=Cauta(node*2,st,mij);
    a2=Cauta(node*2+1,mij+1,dr);
    arb r;
    r.prefix=max(a1.prefix,a1.tot+a2.prefix);
    r.sufix=max(a2.sufix,a2.tot+a1.sufix);
    r.tot=a2.tot+a1.tot;
    r.ans=max(a1.ans,max(a2.ans,a1.sufix+a2.prefix));

    return r;

}


int main()
{
    f>>n;
    int t;
    f>>t;
    for(int i=1;i<=n;++i)
    {
        f>>val;
        poz=i;
        Up(1,1,n);
    }
    for(int i=1;i<=t;++i)
    {
        f>>start>>finish;
        arb ras=Cauta(1,1,n);
        g<<ras.ans<<'\n';
    }
}