#include <iostream>
#include <fstream>
#include <climits>
#define int long long
#define nmx 100005
using namespace std;
int n,pz,q,nr,p,arb[4*nmx],starb[4*nmx],drarb[4*nmx],v[nmx],sum[4*nmx];
void build(int st,int dr,int index)
{
    if (st==dr)
    {
        sum[index]=arb[index]=starb[index]=drarb[index]=v[st];
        return;
    }
    int mid=(st+dr)/2;
    build(st,mid,index*2);
    build(mid+1,dr,index*2+1);
    sum[index]=sum[index*2]+sum[index*2+1];
    starb[index]=max(starb[index*2],sum[index*2]+starb[index*2+1]);
    drarb[index]=max(drarb[index*2+1],drarb[index*2]+sum[index*2+1]);
    arb[index]=max(starb[index],max(drarb[index],max(starb[index*2+1]+drarb[index*2],max(arb[index*2],arb[index*2+1]))));
}
void show(int st,int dr,int index)
{
    cout<<starb[index]<<' '<<drarb[index]<<' '<<arb[index]<<' '<<sum[index]<<' '<<st<<' '<<dr<<'\n';
    if (st==dr)
        return;
    int mid=(st+dr)/2;
    show(st,mid,index*2);
    show(mid+1,dr,index*2+1);
}
struct edge
{
    int ar,st,dr,sum;
};
edge query(int st,int dr,int a,int b,int index)
{
    if (a<=st && dr<=b)
        return {arb[index],starb[index],drarb[index],sum[index]};
    int mid=(st+dr)/2;
    if (a<=mid && mid<b)
    {
        edge c=query(st,mid,a,b,index*2);
        edge d=query(mid+1,dr,a,b,index*2+1);
        edge e;
        e.sum=c.sum+d.sum;
        e.st=max(c.st,c.sum+d.st);
        e.dr=max(d.dr,d.sum+c.dr);
        e.ar=max(e.st,max(max(e.dr,c.dr+d.st),max(c.ar,d.ar)));
        return e;
    }
    else if (a<=mid)
        return query(st,mid,a,b,index*2);
    else if (mid<a)
        return query(mid+1,dr,a,b,index*2+1);
}
int32_t main()
{
    ifstream f ("sequencequery.in");
    ofstream g ("sequencequery.out");
    f>>n>>q;
    for (int i=1; i<=n; i++)
        f>>v[i];
    build(1,n,1);
    //show(1,n,1);
    for (int i=1; i<=q; i++)
    {
        int a,b;
        f>>a>>b;
        edge c=query(1,n,a,b,1);
        g<<c.ar<<'\n';
    }
}