#include<iostream>
#include<fstream>
#define DN 132200
#define INF 20000000000
using namespace std;
fstream fin("sequencequery.in",ios::in),fout("sequencequery.out",ios::out);
class e
{
public:
    e(){}
    e(int val){
        st=dr=mij=all=val;
    }
    long long st,dr,mij,all;
};
e arb[2*DN];
long long n,m,p1,p2,p,poz,st,dr,rst,ras,val;
void query(int nod,int l,int r)
{
    int m=(l+r)/2,f1=nod*2,f2=nod*2+1;
    if(st<=l && r<=dr)
    {
        ras=max(max(ras,arb[nod].mij),rst+arb[nod].st);
        rst=max(rst+arb[nod].all,arb[nod].dr);
        return ;
    }
    if(st<=m) query(f1,l,m);
    if(m<dr)  query(f2,m+1,r);
}
void update(int nod,int l,int r)
{
    int i,m=(l+r)/2,f1=nod*2,f2=nod*2+1;
    if(l==r)
    {
        arb[nod]=e(val);
        return ;
    }
    if(poz<=m) update(f1,l,m);
    if(m<poz)  update(f2,m+1,r);

    arb[nod].st=max(arb[f1].st,arb[f1].all+arb[f2].st);
    arb[nod].dr=max(arb[f2].dr,arb[f1].dr+arb[f2].all);
    arb[nod].mij=max(max(arb[f1].mij,arb[f2].mij),arb[f1].dr+arb[f2].st);
    arb[nod].all=arb[f1].all+arb[f2].all;
}
void build()
{
    int i,f1,f2;
    for(i=p1-1;i>0;i--)
    {
        arb[i].st=max(arb[f1].st,arb[f1].all+arb[f2].st);
        arb[i].dr=max(arb[f2].dr,arb[f1].dr+arb[f2].all);
        arb[i].mij=max(max(arb[f1].mij,arb[f2].mij),arb[f1].dr+arb[f2].st);
        arb[i].all=arb[f1].all+arb[f2].all;
    }
}
int main()
{
    int i,a,b,c;
    fin>>n>>m;
    for(p=1;p<n;p=p*2);
    p1=p;p2=p1+n-1;p=p*2;
    for(i=1;i<=n;i++)
    {
        fin>>val;poz=i;
        update(1,1,n);
    }
    //build();

    for(i=1;i<=m;i++)
    {
        fin>>st>>dr;
        rst=ras=-INF;
        query(1,1,n);
        fout<<ras<<"\n";
    }
}