#include <iostream>
#include <fstream>

using namespace std;

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

#define ll long long int

const int kMaxSize = 100'000;

ll sir[4 * kMaxSize + 5];

struct Seq
{
  ll full_seq;
  ll left_seq;
  ll right_seq;
  ll max_seq;

}arb_int[kMaxSize + 5];

Seq BuildParent(Seq child_l,Seq child_r)
{
  Seq arb;
  arb.full_seq = child_l.full_seq + child_r.full_seq;

  arb.left_seq = max(child_l.left_seq,
    child_l.full_seq + child_r.left_seq);

  arb.right_seq = max(child_r.right_seq,
    child_r.full_seq + child_l.right_seq);

  arb.max_seq = max(max(child_l.max_seq, child_r.max_seq),
    child_l.right_seq + child_r.left_seq);

  return arb;
}

void Build(int nod, int st, int dr)
{
  if (st == dr)
  {
    arb_int[nod].full_seq = sir[st];
    arb_int[nod].left_seq = sir[st];
    arb_int[nod].right_seq = sir[st];
    arb_int[nod].max_seq = sir[st];
  }
  else
  {
    int mij = (st + dr) / 2;
    Build(2 * nod, st, mij);
    Build(2 * nod + 1, mij + 1, dr);
    arb_int[nod] = BuildParent(arb_int[2 * nod], arb_int[2 * nod + 1]);
  }
}

Seq Query(int nod, int st, int dr, int q_st, int q_dr)
{
  if (st >= q_st && dr <= q_dr)
    return arb_int[nod];
  int mij = (st + dr) / 2;
  if (q_dr <= mij)
    return Query(2 * nod, st, mij, q_st, q_dr);
  else if (q_st > mij)
    return Query(2 * nod + 1, mij + 1, dr, q_st, q_dr);
  else
    return BuildParent(Query(2 * nod, st, mij, q_st, q_dr), Query(2 * nod + 1, mij + 1, dr, q_st, q_dr));
}

int main()
{
  int nr_elem, nr_comm;
  ll v[100];

  fin >> nr_elem >> nr_comm;
  for (int i = 1;i <= nr_elem;++i)
  {
    fin >> sir[i];
  }

  Build(1, 1, nr_elem);

  for (int i = 1;i <= nr_comm;++i)
  {
    int q_st, q_dr;
    fin >> q_st >> q_dr;
    fout << Query(1, 1, nr_elem, q_st, q_dr).max_seq << "\n";
  }
}