#include <bits/stdc++.h>
using namespace std;
ifstream fin ("sequencequery.in");
ofstream fout ("sequencequery.out");
int n, m;
const int INF = 1e9;
struct Nod{
    int sum, psum, ssum, ssmax;
};
Nod arbi[400005];
Nod nodupdate(Nod st, Nod dr)
{
    Nod ans;
    ans.sum=st.sum+dr.sum;
    ans.psum=max(st.psum, st.sum+dr.psum);
    ans.ssum=max(dr.ssum, dr.sum+st.ssum);
    ans.ssmax=max(max(st.ssmax, dr.ssmax), st.ssum+dr.psum);
    return ans;
}
void update(int nod, int st, int dr, int val, int pozi)
{
    if(st==dr)
    {
        arbi[nod]={val, val, val, val};
        return;
    }
    int mij=(st+dr)/2;
    if(pozi<=mij)
        update(nod*2, st, mij, val, pozi);
    else
        update(nod*2+1, mij+1, dr, val, pozi);
    arbi[nod]=nodupdate(arbi[nod*2], arbi[nod*2+1]);
    return;
}
Nod query(int nod, int st, int dr, int qst, int qdr)
{
    if(qst<=st && dr<=qdr)
        return arbi[nod];
    if(qdr<st || dr<qst)
    {
        Nod aux={-INF, -INF, -INF, -INF};
        return aux;
    }
    int mij=(st+dr)/2;
    return nodupdate(query(nod*2, st, mij, qst, qdr),query(nod*2+1, mij+1, dr, qst, qdr));
}
void citti()
{
    fin>>n>>m;
    int x;
    for(int i=1; i<=n; i++)
    {
        fin>>x;
        update(1, 1, n, x, i);
    }
}
void rezi()
{
    int c,p;
    for(int i=1; i<=m; i++)
    {
        fin>>c>>p;
        fout<<query(1, 1, n, c, p).ssmax<<'\n';
    }
}
int main()
{
    citti();
    rezi();
    return 0;
}