#include <fstream>
#import <algorithm>
#import <vector>
#import <map>
#import <deque>
#import <cassert>
#import <cmath>
using namespace std;
#define int long long
ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
struct x
{
    int sum,sum_max,pre,suf;
};
x add(const x& a,const x& b)
{
    x rez;
    rez.sum=a.sum+b.sum;
    rez.pre=max(a.pre,a.sum+b.pre);
    rez.suf=max(b.suf,b.sum+a.suf);
    rez.sum_max=max(max(max(a.sum_max,b.sum_max),max(rez.pre,rez.suf)),a.suf+b.pre);
    return rez;
}

x aint[400001];
int v[100001],n;
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        aint[nod].sum=v[st];
        aint[nod].sum_max=v[st];
        aint[nod].suf=v[st];
        aint[nod].pre=v[st];
        return;
    }
    int m=(st+dr)/2;
    build(2*nod,st,m);
    build(2*nod+1,m+1,dr);
    aint[nod]=add(aint[2*nod],aint[2*nod+1]);
}
int caut;
int l,r;
x reza;
void query(int nod,int st,int dr)
{
    if(st>r || dr<l)return;
    if(l<=st && r>=dr)
    {
        if(reza.sum_max==-2e9)reza=aint[nod];
        else reza=add(reza,aint[nod]);
        return;
    }
    int m=(st+dr)/2;
    query(2*nod,st,m);
    query(2*nod+1,m+1,dr);


}
main()
{
    int q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>v[i];
    build(1LL,1LL,n);
    while(q--)
    {
        cin>>l>>r;
        reza.sum_max=reza.sum=reza.pre=reza.suf=-2e9;
        query(1LL,1LL,n);
        cout<<reza.sum_max<<'\n';
    }
}