#include <fstream>
#include <cmath>

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

const long long INF = (1LL<<62);
const int DIM = 100005;

int n,q,v[DIM],a,b,nr,last;

long long ans;

struct SegmentTree
{
    long long Sum,St,Dr,Best;
}Tree[DIM*4+5];

long long max(long long a, long long b)
{
    if(a>b)
        return a;
    return b;
}

void Read()
{
    fin>>n>>q;
    for(int i=1;i<=n;i++)
            fin>>v[i];
}

void UpdateValues(int nod)
{
    Tree[nod].Sum=Tree[2*nod].Sum+Tree[2*nod+1].Sum;
    Tree[nod].St=max(max(Tree[2*nod+1].St,Tree[2*nod+1].Sum),0)+Tree[2*nod].Sum;
    Tree[nod].Dr=max(max(Tree[2*nod].Dr,Tree[2*nod].Sum),0)+Tree[2*nod+1].Sum;
    Tree[nod].Best=max(max(Tree[nod].St,Tree[nod].Dr),max(Tree[nod].Sum,(Tree[2*nod].Dr+Tree[2*nod+1].St)));
}

void BuildTree(int nod, int st, int dr)
{
    if(st==dr)
        {
            Tree[nod].Sum=Tree[nod].St=Tree[nod].Dr=Tree[nod].Best=v[st];
            return;
        }
    int mij=(st+dr)>>1;
    BuildTree(2*nod,st,mij);
    BuildTree(2*nod+1,mij+1,dr);
    UpdateValues(nod);
}

void QueryTree(int nod, int st, int dr, int a, int b)
{
    if(st>=a && dr<=b)
        {
            nr++;
            ans=max(ans,max(max(Tree[nod].Sum,Tree[nod].St),max(Tree[nod].Dr,Tree[nod].Best)));
            if(nr>1)
                    ans=max(ans,last+max(Tree[nod].St,Tree[nod].Sum));
            last=max(0,max(last,last+max(Tree[nod].Sum,Tree[nod].Dr)));
            return;
        }
    int mij=(st+dr)>>1;
    if(a<=mij)
        QueryTree(2*nod,st,mij,a,b);
    if(b>mij)
        QueryTree(2*nod+1,mij+1,dr,a,b);
}

void Query()
{
    while(q--)
        {
            fin>>a>>b;
            ans=-INF;nr=0;last=0;
            QueryTree(1,1,n,a,b);
            fout<<ans<<'\n';
        }
}

int main()
{
    Read();
    BuildTree(1,1,n);
    Query();
}