#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],rez;
long long x,y;
int n,m,ok;

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)
    {
        if(ok)
        {
            rez=arb[nod];
            ok=0;
        }
        else
        {
            rez.smax=max(arb[nod].smax,max(rez.smax,rez.slt+arb[nod].srt));
            rez.slt=max(arb[nod].slt,rez.slt+arb[nod].stot);
            rez.stot+=arb[nod].stot;
        }
        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;
        ok=1;
        query(1,1,n,x,y);
        g<<rez.smax<<'\n';
    }
    return 0;
}