#include <bits/stdc++.h>
#define Nmax 100005
#define ll long long
#define ls (nod<<1)
#define rs (ls+1)
#define INF (1LL<<62)
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
ll s[Nmax];
struct Segment_Tree
{
    ll lo,hi,sum,best;
};
Segment_Tree Aint[Nmax<<2];
int n,Q,lsh,rsh,i;
ll ans,S;
void build(int p, int q, int nod)
{
    if(p==q) Aint[nod]={s[p],s[p],s[p],s[p]};
    else
    {
        int m=(p+q)>>1;
        build(p,m,ls);
        build(m+1,q,rs);
        Aint[nod].lo=max(Aint[ls].lo,Aint[ls].sum+Aint[rs].lo);
        Aint[nod].hi=max(Aint[rs].hi,Aint[rs].sum+Aint[ls].hi);
        Aint[nod].best=max(Aint[ls].hi+Aint[rs].lo,max(Aint[ls].best,Aint[rs].best));
        Aint[nod].sum=Aint[ls].sum+Aint[rs].sum;
    }
}
void query(int p, int q, int nod)
{
    if(lsh<=p and q<=rsh)
    {
        ans=max(ans,max(S+Aint[nod].lo,Aint[nod].best));
        S=max(S+Aint[nod].sum,Aint[nod].hi);
    }
    else
    {
        int m=(p+q)>>1;
        if(lsh<=m) query(p,m,ls);
        if(m<rsh) query(m+1,q,rs);
    }
}
int main()
{
    f>>n>>Q;
    for(i=1;i<=n;i++)
        f>>s[i];
    build(1,n,1);
    while(Q--)
    {
        f>>lsh>>rsh;
        ans=S=-INF;
        query(1,n,1);
        g<<ans<<'\n';
    }

    return 0;
}