#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e5;
struct Nod {
  long long sum, pref, suf, ssm;
} aint[4 * N + 2];
long long n, x, y, q;

long long ans, aux;
void update (long long nod, long long st, long long dr,  long long poz, long long val) {
  if (st == dr)
    aint[nod].sum = aint[nod].pref = aint[nod].suf = aint[nod].ssm = val;
  else {
    long long mid = (st + dr) / 2;
    if (poz <= mid)
      update (2 * nod, st, mid, poz, val);
    if (poz > mid)
      update (2 * nod + 1, mid + 1, dr, poz, val);
    aint[nod].sum = aint[2 * nod].sum + aint[2 * nod + 1].sum;
    aint[nod].pref = max(aint[2 * nod].pref, aint[2 * nod].sum + aint[2 * nod + 1].pref);
    aint[nod].suf = max(aint[2 * nod + 1].suf, aint[2 * nod + 1].sum + aint[2 * nod].suf);
    aint[nod].ssm = max(max(aint[2 * nod].ssm, aint[2 * nod + 1].ssm), aint[2 * nod].suf + aint[2 * nod + 1].pref);
  }
}

void query (long long nod, long long st, long long dr, long long a, long long b) {
  if (a <= st && dr <= b) {
    ans = max(ans, max(aux + aint[nod].pref, aint[nod].ssm));
    aux = max(0LL, max(aint[nod].suf, aux + aint[nod].sum));
  }
  else {
    long long mid = (st + dr) / 2;
    if (a <= mid)
      query (2 * nod, st, mid, a, b);
    if (b >= mid + 1)
      query (2 * nod + 1, mid + 1, dr, a, b);
  }
}

int main()
{
  fin >> n >> q;
  for (int i = 1; i <= n; i++) {
    fin >> x;
    update(1, 1, n, i, x);
  }
  for (int i = 1; i <= q; i++) {
    fin >> x >> y;
    ans = -1000000000;
    aux = 0;
    query(1, 1, n, x, y);
    fout << ans << "\n";
  }
  return 0;
}