#include <bits/stdc++.h>
#define LIM 1<<17
#define INF 1000000000000LL
/// TONI BO$$ was here
/// #MLC

using namespace std;
char BUF[LIM];
int poz;

inline char getChar(){
    poz++;
    if(poz>=LIM){
    	fread(BUF,LIM,1,stdin);
    	poz=0;
    }
    return BUF[poz];
}

inline int getNr(){
    int r=0, semn=1;
    char ch=getChar();
    while(isdigit(ch)==0 && ch!='-') ch=getChar();
    if(ch=='-'){
        semn=-1;
        ch=getChar();
    }
    while(isdigit(ch)!=0){
        r=r*10+semn*(ch-'0');
        ch=getChar();
    }
    return r;
}

int v[100001];
struct gogu
{
    long long pref,suf,secv,ssm;
}arbint[300001];

void init(int i,long long x,int st,int dr,int nod)
{
    if(st==dr && st==i && dr==i)
    {
        arbint[nod]={x,x,x,x};
        return ;
    }
    if(st==dr)
        return ;
    int mij=(st+dr)/2;
    if(i<=mij)
        init(i,x,st,mij,2*nod);
    else
        init(i,x,mij+1,dr,2*nod+1);
}

void build(int st,int dr,int nod)
{
    if(st==dr)
        return ;
    int mij=(st+dr)/2;
    build(st,mij,2*nod);
    build(mij+1,dr,2*nod+1);
    arbint[nod].pref=max(arbint[2*nod].pref,arbint[2*nod].secv+arbint[2*nod+1].pref);
    arbint[nod].suf=max(arbint[2*nod+1].suf,arbint[2*nod+1].secv+arbint[2*nod].suf);
    arbint[nod].secv=arbint[2*nod].secv+arbint[2*nod+1].secv;
    arbint[nod].ssm=max(arbint[2*nod].ssm,arbint[2*nod+1].ssm);
    arbint[nod].ssm=max(arbint[nod].ssm,arbint[nod].pref);
    arbint[nod].ssm=max(arbint[nod].ssm,arbint[nod].suf);
    arbint[nod].ssm=max(arbint[nod].ssm,arbint[nod].secv);
    arbint[nod].ssm=max(arbint[nod].ssm,arbint[2*nod].suf+arbint[2*nod+1].pref);
}

gogu query(int x,int y,int st,int dr,int nod)
{
    gogu z1,z2,rez;
    z1=z2={-INF,-INF,0,-INF};
    if(st>=x && dr<=y)
        return arbint[nod];
    int mij=(st+dr)/2;
    if(x<=mij)
        z1=query(x,y,st,mij,2*nod);
    if(y>mij)
        z2=query(x,y,mij+1,dr,2*nod+1);
    rez.secv=z1.secv+z2.secv;
    rez.pref=max(z1.pref,z1.secv+z2.pref);
    rez.suf=max(z2.suf,z2.secv+z1.suf);
    rez.ssm=max(z1.ssm,z2.ssm);
    rez.ssm=max(rez.ssm,z1.suf+z2.pref);
    rez.ssm=max(rez.ssm,rez.pref);
    rez.ssm=max(rez.ssm,rez.suf);
    rez.ssm=max(rez.ssm,rez.secv);
    return rez;

}

int main()
{
    int n,m,i,x,y;
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    n=getNr();
    m=getNr();
    for(i=1; i<=n; i++)
    {
        v[i]=getNr();
        init(i,v[i],1,n,1);
    }
    build(1,n,1);
    while(m--)
    {
        x=getNr();
        y=getNr();
        gogu z=query(x,y,1,n,1);
        printf("%lld\n",z.ssm);
    }

    return 0;
}