#include <bits/stdc++.h>
using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
typedef long long ll;
const ll lim=1e5+4;
struct node
{
    ll st;
    ll dr;
    ll med;
    ll sum;
}tree[4*lim];
ll v[lim],n,m,x,y;
void comp(node &s,node a,node b);
void build(ll nod,ll l,ll r)
{
    if(l==r)
    {
        tree[nod]={v[l],v[l],v[l],v[l]};
        return ;
    }
    ll med=(l+r)>>1;
    build(2*nod,l,med);
    build(2*nod+1,med+1,r);
    comp(tree[nod],tree[2*nod],tree[2*nod+1]);
}
node query(ll nod,ll l,ll r,ll a,ll b)
{
    if(a<=l and r<=b)
        return tree[nod];
    node ans1,ans2,ans;
    ll med=(l+r)>>1;
    if(a<=med and b>med)
    {
        ans1=query(2*nod,l,med,a,b);
        ans2=query(2*nod+1,med+1,r,a,b);
        comp(ans,ans1,ans2);
        return ans;
    }
    if(a<=med)
        return query(2*nod,l,med,a,b);
    return query(2*nod+1,med+1,r,a,b);
}
void comp(node &s,node a,node b)
{
    s.st=max({a.st,a.sum+b.st});
    s.dr=max({b.dr,b.sum+a.dr});
    s.med=max({a.med,b.med,a.dr+b.st});
    s.sum=a.sum+b.sum;
}
int main()
{
    in>>n>>m;
    for(ll i=1;i<=n;++i)
        in>>v[i];
    build(1,1,n);
    while(m--)
    {
        in>>x>>y;
        out<<query(1,1,n,x,y).med<<'\n';
    }
    return 0;
}