#include <iostream>
#include <fstream>
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
const long long inf=-(1LL<<62);
struct {
    long long stot,smax,slt,srt;
}arb[400005];
long long n,m,x,y,rez,SUML,SUMR,SUMT,r;

void build(int nod,int lt,int rt,int pos)
{
    if(lt==rt)
    {
        arb[nod].slt=arb[nod].smax=arb[nod].srt=arb[nod].stot=x;
        return;
    }
    int md=(lt+rt)/2;
    if(pos<=md) build(nod*2,lt,md,pos);
    else build(nod*2+1,md+1,rt,pos);

    arb[nod].smax=max(arb[nod*2].smax,max(arb[nod*2].slt+arb[nod*2+1].srt,arb[nod*2+1].smax));
    arb[nod].slt=max(arb[nod*2+1].slt,arb[nod*2+1].stot+arb[nod*2].slt);
    arb[nod].srt=max(arb[nod*2].srt,arb[nod*2].stot+arb[nod*2+1].srt);
    arb[nod].stot=arb[nod*2].stot+arb[nod*2+1].stot;
}

void query(int nod,int lt,int rt,int x,int y)
{
    if(lt>y || rt<x) return;
    if(x<=lt && rt<=y)
    {
        ++r;
        if(r==1)
        {
            SUML=SUMT=arb[nod].slt;
        }
        else if(r==2)
        {
            SUML+=arb[nod].srt;
            SUMT+=arb[nod].stot;
            SUMR=arb[nod].slt;
        }
        else
        {
            SUMR+=arb[nod].srt;
            SUMT+=arb[nod].srt;
        }
        rez=max(rez,arb[nod].smax);
        return;
    }
    if(lt==rt) return;
    int md=(lt+rt)/2;
    if(md>=x) query(nod*2,lt,md,x,y);
    if(md<y) query(nod*2+1,md+1,rt,x,y);
}

void afisare()
{
    int d=0;
    for(int i=1;i<=4;++i)
    {
        for(int j=1;j<=(1<<(i-1));++j)
        {
            ++d;
            cout<<arb[d].smax<<' ';
        }
        cout<<endl;
    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=n;++i)
    {
        f>>x;
        build(1,1,n,i);
    }
    //afisare();
    for(int i=1;i<=m;++i)
    {
        f>>x>>y;
        r=0;
        rez=SUML=SUMR=SUMT=inf;
        query(1,1,n,x,y);
        rez=max(max(rez,SUMT),max(SUML,SUMR));
        g<<rez<<'\n';
    }
    return 0;
}