#include <bits/stdc++.h>
#define dim 100005
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
int n,m;
struct arbore
{
    long long prefix,sufix,sum,ans;
}arb[4*dim];
arbore Unite(arbore a,arbore b)
{
    arbore sol;
    sol.sum=a.sum+b.sum;
    sol.prefix=max(a.prefix,a.sum+b.prefix);
    sol.sufix=max(b.sufix,b.sum+a.sufix);
    sol.ans=max(max(a.ans,b.ans),a.sufix+b.prefix);
    return sol;
}
void Update(int node,int st,int dr,int pos,int val)
{
    if(st==dr)
    {
        arb[node].ans=arb[node].prefix=arb[node].sufix=arb[node].sum=val;
        return;
    }
    int mij=(st+dr)/2;
    if(pos<=mij)
        Update(2*node,st,mij,pos,val);
    else
        Update(2*node+1,mij+1,dr,pos,val);
    arb[node]=Unite(arb[2*node],arb[2*node+1]);
}
arbore Query(int node,int st,int dr,int start,int finish)
{
    if(start<=st&&dr<=finish)
        return arb[node];
    int mij=(st+dr)/2;
    if(start<=mij&&mij<finish)
    {
        arbore arb1,arb2;
        arb1=Query(2*node,st,mij,start,finish);
        arb2=Query(2*node+1,mij+1,dr,start,finish);
        return Unite(arb1,arb2);
    }
    if(start<=mij)return Query(2*node,st,mij,start,finish);
    if(mij<finish)return Query(2*node+1,mij+1,dr,start,finish);
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;++i)
    {
        int x;
        f>>x;
        Update(1,1,n,i,x);
    }
    for(int i=1;i<=m;++i)
    {
        int x,y;
        f>>x>>y;
        g<<Query(1,1,n,x,y).ans<<"\n";
    }
    return 0;
}