#include <fstream>
#define INF 1e9
using namespace std;
struct Arb
{
    long long ans,pref,suf,suma;
}t[300005];
long long v[100005],val,sufmax,Start,End;
void build(int node,int st,int dr)
{
    if(st==dr)
    {
        t[node].ans = t[node].suf = t[node].pref = t[node].suma = v[st];
        t[node].suma=v[st];
    }
    else
    {
        int mij=(st+dr)/2;
        build(2*node,st,mij);
        build(2*node+1,mij+1,dr);
        t[node].suma=t[2*node].suma+t[2*node+1].suma;
        t[node].suf=max(t[2*node].suf+t[2*node+1].suma,t[2*node+1].suf);
        t[node].pref=max(t[2*node].pref,t[2*node+1].pref+t[2*node].suma);
        t[node].ans=max(t[2*node].ans,max(t[2*node+1].ans,t[2*node].suf+t[2*node+1].pref));
    }
}
void query(int node,int st,int dr)
{
    if(Start<=st && dr<=End)
        val=max(val,t[node].ans),val=max(val,t[node].pref+sufmax),sufmax=max(sufmax+t[node].suma,t[node].suf);
    else
    {
        int mij=(st+dr)/2;
        if(Start<=mij)
            query(2*node,st,mij);
        if(mij+1<=End)
            query(2*node+1,mij+1,dr);
    }
}
int main()
{
    ifstream cin("sequencequery.in");
    ofstream cout("sequencequery.out");
    int n,m,x,y;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        val=-INF,sufmax=0,Start=x,End=y;
        query(1,1,n);
        cout<<val<<'\n';
    }
    return 0;
}