#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int n,m,i,j,x,y,v;
long long s,rez;

long long arb[400001],l[400001],r[400001],sum[400001];
void build(int nod,int poz,int val,int st,int dr)
{
    int mij=(st+dr)/2;
    if(st==dr)
    {
        if(st==poz)
        {
            arb[nod]=val;sum[nod]=val;
            l[nod]=val;r[nod]=val;
        }

        return;
    }
    build(nod*2,poz,val,st,mij);
    build(nod*2+1,poz,val,mij+1,dr);
    sum[nod]=sum[nod*2]+sum[nod*2+1];
    l[nod]=max(l[nod*2],sum[nod*2]+l[nod*2+1]);
    r[nod]=max(r[nod*2+1],sum[nod*2+1]+r[nod*2]);
    arb[nod]=max(sum[nod],max(l[nod],r[nod]));

}
void query(int nod,int ls,int ld,int st,int dr)
{
    int mij=(st+dr)/2;
    if(ls<=st && ld>=dr)
    {
        rez=max(rez,max(s+l[nod],arb[nod]));
        s=max(s+sum[nod],r[nod]);
        return;
    }
    if(ld<st or ls>dr) return;
    if(ls<=mij)query(nod*2,ls,ld,st,mij);
    if(ld>mij)query(nod*2+1,ls,ld,mij+1,dr);
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fin>>v;
        build(1,i,v,1,n);
    }
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        rez=s=-(1LL<<30);
        query(1,x,y,1,n);
        fout<<rez<<'\n';
    }
    return 0;
}