#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N=1e5+5;
int v[N];
struct Node
{
    int ss,pref,suf,mx;
};
Node aint[4*N];
void reset(int node, int l)
{
    aint[node].ss=aint[node].pref=aint[node].suf=aint[node].mx=v[l];
}
void combine(Node &c, Node a, Node b)
{
    c.ss=a.ss+b.ss;
    c.pref=max(a.pref,a.ss+b.pref);
    c.suf=max(b.suf,a.suf+b.ss);
    c.mx=max({a.mx,b.mx,a.suf+b.pref});
}
void build(int node, int l, int r)
{
    if(l==r) {reset(node,l);return;}
    int mij=(l+r)/2;
    build(node*2,l,mij);
    build(node*2+1,mij+1,r);
    combine(aint[node],aint[node*2],aint[node*2+1]);
}
Node ans;
void query(int node, int l, int r, int ql, int qr)
{
    if(qr<l||r<ql) return;
    if(ql<=l&&r<=qr) {combine(ans,ans,aint[node]);return;}
    int mij=(l+r)/2;
    query(node*2,l,mij,ql,qr);
    query(node*2+1,mij+1,r,ql,qr);
}
signed main()
{
    ifstream cin("sequencequery.in");ofstream cout("sequencequery.out");
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;++i) cin>>v[i];
    build(1,1,n);
    cout<<'\n';
    while(q--)
    {
        int l,r;cin>>l>>r;
        ans.ss=ans.pref=0;ans.suf=ans.mx=-1e18;
        query(1,1,n,l,r);
        cout<<ans.mx<<'\n';
    }
}