#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
#define ll long long int
const int kMaxSize = 100000;
int sir[kMaxSize + 5];
struct Seq
{
  ll full_seq;
  ll left_seq;
  ll right_seq;
  ll max_seq;

}arb_int[4 * kMaxSize + 5];

Seq Comb(Seq a,Seq b)
{
    Seq nod;
    nod.full_seq=a.full_seq + b.full_seq;

    nod.left_seq=max(a.left_seq,a.full_seq+b.left_seq);

    nod.right_seq=max(b.right_seq,b.full_seq+a.right_seq);

    nod.max_seq=max(a.right_seq+b.left_seq,max(a.max_seq,b.max_seq));

    return nod;
}

void Build(int nod, int st, int dr)
{
    int mij=(st+dr)/2;
    if(st==dr)
        arb_int[nod]={sir[st],sir[st],sir[st],sir[st]};
    else
    {
        Build(2*nod,st,mij);
        Build(2*nod+1,mij+1,dr);
        arb_int[nod]=Comb(arb_int[2*nod],arb_int[2*nod+1]);
    }
}

Seq Query(int nod, int st, int dr, int q_st, int q_dr)
{
    int mij=(st+dr)/2;
    if(st<=q_st && q_dr<=dr)
        return arb_int[nod];
    if(q_st>mij)
        return Query(2*nod, st, mij, q_st, q_dr);
    if(q_dr<mij)
        return Query(2*nod+1, mij+1, dr, q_st, q_dr);
    else
        return Comb(Query(nod*2, st, mij, q_st, q_dr),Query(2*nod+1, mij+1, dr, q_st, q_dr));
}
int main()
{
    int nr, perechi;
    fin>>nr>>perechi;
    for(int i=1; i<=nr; ++i)
        fin>>sir[i];
    Build(1, 1, nr);
    for(int i=0; i<perechi; ++i)
    {
        int q_st, q_dr;
        fin>>q_st>>q_dr;
        fout<<Query(1, 1, nr, q_st, q_dr).max_seq<<"\n";
    }
}