#include <bits/stdc++.h>

using namespace std;

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

struct structura
{
    int prefix;
    int sufix;
    int subseq;
    int sum;
};

int v[100003];
structura aint[400003];
int n,m,rasp,sufmax;

void update(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod].prefix=v[st];
        aint[nod].sufix=v[st];
        aint[nod].subseq=v[st];
        aint[nod].sum=v[st];
        return;
    }
    int mij=(st+dr)/2;
    update(2*nod,st,mij);
    update(2*nod+1,mij+1,dr);
    aint[nod].prefix=max(aint[2*nod].prefix, aint[2*nod].sum+aint[2*nod+1].prefix);
    aint[nod].sufix=max(aint[2*nod+1].sufix, aint[2*nod+1].sum+aint[2*nod].sufix);
    aint[nod].sum=aint[2*nod].sum+aint[2*nod+1].sum;
    aint[nod].subseq=max(aint[2*nod].subseq,
                         max(aint[2*nod+1].subseq, aint[2*nod+1].prefix+aint[2*nod].sufix));
}

void query(int nod, int st, int dr, int a, int b)
{
    if(st==a && dr==b)
    {
        rasp = max(rasp, max(aint[nod].subseq,aint[nod].prefix+sufmax));
        sufmax = max(aint[nod].sufix,aint[nod].sum+sufmax);
        return;
    }
    int mij=(st+dr)/2;
    if(b<=mij)
    {
        query(2*nod,st,mij,a,b);
    }
    else if(a>mij)
    {
        query(2*nod+1,mij+1,dr,a,b);
    }
    else
    {
        query(2*nod,st,mij,a,mij);
        query(2*nod+1,mij+1,dr,mij+1,b);
    }
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        fin>>v[i];
    }
    update(1,1,n);
    for(int i=0; i<m; i++)
    {
        int a,b;
        fin>>a>>b;
        rasp=-1000000;
        sufmax=0;
        query(1,1,n,a,b);
        fout<<rasp<<"\n";
    }
    return 0;
}