#include <fstream>

using namespace std;

ifstream cin ("sequencequery.in");
ofstream cout ("sequencequery.out");

int n, q, x, y;

struct Arbint {
  long long mx, sum, pref, suff;
} aint[400005];

Arbint best(Arbint st, Arbint dr) {
  Arbint nod;
  nod.mx = max(max(st.mx, dr.mx), st.suff + dr.pref);
  nod.sum = st.sum + dr.sum;
  nod.pref = max(st.pref, st.sum + dr.pref);
  nod.suff = max(dr.suff, dr.sum + st.suff);
  return nod;
}

void update(int nod, int st, int dr, int poz, int val) {
  if(st == dr) {
    aint[nod] = {val, val, val, val};
    return;
  }
  int mid = (st + dr) >> 1;
  if(poz <= mid)
    update(2 * nod, st, mid, poz, val);
  else
    update(2 * nod + 1, mid + 1, dr, poz, val);
  aint[nod] = best(aint[2 * nod], aint[2 * nod + 1]);
}

Arbint query(int nod, int st, int dr, int l, int r) {
  if(l <= st && dr <= r)
    return aint[nod];
  int mid = (st + dr) >> 1;
  if(r <= mid)
    return query(2 * nod, st, mid, l, r);
  else if(mid < l)
    return query(2 * nod + 1, mid + 1, dr, l, r);
  else
    return best(query(2 * nod, st, mid, l, mid), query(2 * nod + 1, mid + 1, dr, mid + 1, r));
}

int main() {
  cin >> n >> q;
  for(int i = 1; i <= n; i++) {
    cin >> x;
    update(1, 1, n, i, x);
  }
  for(; q; q--) {
    cin >> x >> y;
    cout << query(1, 1, n, x, y).mx << "\n";
  }
  return 0;
}