#include<fstream>
#include<iostream>
#define DN 100005
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int n,f,l,m,poz,val;
long long a[DN],r[4*DN],rs[4*DN],rd[4*DN],s[4*DN],rez,sum;
void update(int nod,int st,int dr)
{
    if(st==dr)
    {
        r[nod]=rs[nod]=rd[nod]=s[nod]=val;
        return;
    }
    int mij=(st+dr)/2;
    if(poz<=mij)
        update(2*nod,st,mij);
    else
        update(2*nod+1,mij+1,dr);
    r[nod]=max(max(r[2*nod],r[2*nod+1]),rd[2*nod]+rs[2*nod+1]);
    rs[nod]=max(rs[2*nod],s[2*nod]+rs[2*nod+1]);
    rd[nod]=max(rd[2*nod+1],s[2*nod+1]+rd[2*nod]);
    s[nod]=s[2*nod]+s[2*nod+1];
}
void query(int nod,int st,int dr)
{
    if(st>=f&&dr<=l)
    {
        rez=max(rez,max(sum+rs[nod],r[nod]));
        sum=max(sum+s[nod],rd[nod]);
        return;
    }
    int mij=(st+dr)/2;
    if(f<=mij)
        query(2*nod,st,mij);
    if(mij<l)
        query(2*nod+1,mij+1,dr);
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fin>>a[i];
        val=a[i];
        poz=i;
        update(1,1,n);
    }
    for(int i=1;i<=m;i++)
    {
        fin>>f>>l;
        rez=-(1<<28);
        sum=0;
        query(1,1,n);
        fout<<rez<<'\n';
    }
}