#include<fstream>
#include<algorithm>
#include<climits>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
#define int long long
const int Nmax=1e5;
struct Node
{
    int sum,bestPrefix,bestSuffix,bestSubarray;
};
Node Arb[4*Nmax+5];
int v[Nmax+5];
Node unify(Node left,Node right)
{
    Node res;
    res.sum=left.sum+right.sum;
    res.bestPrefix=max(left.bestPrefix,left.sum+right.bestPrefix);
    res.bestSuffix=max(right.bestSuffix,right.sum+left.bestSuffix);
    res.bestSubarray=max({left.bestSubarray,right.bestSubarray,left.bestSuffix+right.bestPrefix});
    return res;
}
void build(int nod,int left,int right)
{
    if(left==right)
    {
        Arb[nod]= {v[left],v[left],v[left],v[left]};
        return;
    }
    int mid=(left+right)/2;
    build(2*nod,left,mid);
    build(2*nod+1,mid+1,right);
    Arb[nod]=unify(Arb[2*nod],Arb[2*nod+1]);
}
void query(int left,int right,int qleft,int qright,int nod,Node &res)
{
    if(left>qright||right<qleft)
    {
        res= {-LLONG_MAX,-LLONG_MAX,-LLONG_MAX,-LLONG_MAX};
        return;
    }
    if(qleft<=left&&right<=qright)
    {
        res=Arb[nod];
        return;
    }
    int mid=(left+right)/2;
    Node leftRes,rightRes;
    query(left,mid,qleft,qright,2*nod,leftRes);
    query(mid+1,right,qleft,qright,2*nod+1,rightRes);
    if(leftRes.sum==-LLONG_MAX)res=rightRes;
    else if(rightRes.sum==-LLONG_MAX)res=leftRes;
    else res=unify(leftRes,rightRes);
}
signed main()
{
    int n,q;
    fin>>n>>q;
    for(int i=1; i<=n; i++)
    {
        fin>>v[i];
    }
    build(1,1,n);
    while(q--)
    {
        int a,b;
        fin>>a>>b;
        Node res;
        query(1,n,a,b,1,res);
        fout<<res.bestSubarray<<"\n";
    }
    return 0;
}