#include <bits/stdc++.h>

using namespace std;

ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

int n,m,i,a[100010];

struct cons{
    int Val_Lft=0,Val_Rgt=0,Bst=0,Ind_Lft=0,Ind_Rgt=0,Lft=0,Rgt=0;
}aint[400010];

cons ans;

cons marge(cons a,cons b)
{
    cons ret;
    ret.Lft=a.Lft;ret.Rgt=b.Rgt;

    ret.Val_Lft=a.Val_Lft;
    ret.Ind_Lft=a.Ind_Lft;
    if(a.Ind_Lft==a.Rgt&&b.Val_Lft>=0)
    {
        ret.Val_Lft+=b.Val_Lft;
        ret.Ind_Lft =b.Ind_Lft;
    }

    ret.Val_Rgt=b.Val_Rgt;
    ret.Ind_Rgt=b.Ind_Rgt;
    if(b.Ind_Rgt==b.Lft&&a.Val_Rgt>=0)
    {
        ret.Val_Rgt+=a.Val_Rgt;
        ret.Ind_Rgt =a.Ind_Rgt;
    }

    ret.Bst=max(max(a.Bst,b.Bst),a.Val_Rgt+b.Val_Lft);

    return ret;
}

void caut(int poz,int l,int r,int lo,int hi)
{
    if(lo<=l&&r<=hi)
    {
        ans=marge(ans,aint[poz]);
        return ;
    }
    int mi=(l+r)/2;
    if(lo<=mi)
        caut(poz*2  ,l   ,mi,lo,hi);
    if(mi+1<=hi)
        caut(poz*2+1,mi+1,r ,lo,hi);
    return;
}

void init(int poz,int l,int r)
{
    aint[poz].Lft=l;
    aint[poz].Rgt=r;
    if(l==r)
    {
        aint[poz].Val_Lft=aint[poz].Val_Rgt=aint[poz].Bst=a[l];
        aint[poz].Ind_Lft=aint[poz].Ind_Rgt=l;
        return ;
    }
    int mi=(l+r)/2;
    init(poz*2  ,l   ,mi);
    init(poz*2+1,mi+1,r );
    aint[poz]=marge(aint[poz*2],aint[poz*2+1]);
}

int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
        f>>a[i];
    init(1,1,n);
    for(;m;m--)
    {
        int x,y;
        f>>x>>y;
        ans.Val_Lft=-1e9,ans.Val_Rgt=-1e9,ans.Bst=-1e9,
        ans.Ind_Lft=0,ans.Ind_Rgt=0,
        ans.Lft=x,ans.Rgt=x-1;
        caut(1,1,n,x,y);
        g<<ans.Bst<<'\n';
    }
    return 0;
}