#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#define ll long long
using namespace std;
ifstream fin("sequencequery.in");
ofstream gout("sequencequery.out");
struct desc
{
    ll pre,suf,tot,maxi;
    //void desc(int ppre,int ssuf){
    //pre=ppre;suf=ssuf;}
};
desc merge(desc st,desc dr)
{
    desc ans;
    ans.tot=st.tot+dr.tot;
    ans.pre=max(st.pre,st.tot+dr.pre);
    ans.suf=max(dr.suf,dr.tot+st.suf);
    ans.maxi=max({st.maxi,dr.maxi,st.suf+dr.pre});
    return ans;
}
void build(vector<desc>&a,vector<ll>&v,int u,int l,int r)
{
    if(l==r)a[u]= {v[l],v[l],v[l],v[l]};
    else
    {
        int m=(l+r)/2;
        build(a,v,u*2,l,m);
        build(a,v,u*2+1,m+1,r);
        a[u]=merge(a[u*2],a[u*2+1]);
    }
}
void update(vector<desc>&a,int u,int l,int r,int pos,int &val)
{
    if(l>r)return ;
    if(l==pos&&r==pos)a[u]= {val,val,val,val};
    else
    {
        int m=(l+r)/2;
        if(pos<=m)update(a,u*2,l,m,pos,val);
        else update(a,u*2+1,m+1,r,pos,val);
        a[u]=merge(a[u*2],a[u*2+1]);
    }
}
desc query(vector<desc>&v,int l,int r,int tl,int tr,int u)
{
    if(l>r)return {0,0,0,0};
    if(l==tl&&r==tr)return v[u];
    int m=(tl+tr)/2;
    if(r<=m)return query(v,l,r,tl,m,u*2);
    if(l>m)return query(v,l,r,m+1,tr,u*2+1);
    desc st=query(v,l,m,tl,m,u*2);
    desc dr=query(v,m+1,r,m+1,tr,u*2+1);
    return merge(st,dr);
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    gout.tie(NULL);
    int n,salut,x,y;
    fin>>n>>salut;
    vector<desc>a(n*4+15, {0,0,0,0});
    vector<ll>v(n+1);
    for(int i=0; i<n; ++i)fin>>v[i];
    build(a,v,1,0,n-1);
    while(salut--)
    {
        fin>>x>>y;--x;--y;
            gout<<query(a,x,y,0,n-1,1).maxi<<'\n';
    }
    return 0;
}