#include <cstdio>
#include <algorithm>

using namespace std;

struct Node {
  long long ssm, sum, pref, suf;
}aint[800005];

long long ans1, ans2;

void update(long long node, long long st, long long dr, long long poz, long long val) {
  if (st == dr) {
    aint[node] = {val, val, val, val};
    return ;
  }
  long long med = (st + dr) / 2;
  if (med >= poz)
    update(2 * node, st, med, poz, val);
  else
    update(2 * node + 1, med + 1, dr, poz, val);
  aint[node].ssm = max(max(aint[2 * node].ssm, aint[2 * node + 1].ssm), aint[2 * node].suf + aint[2 * node + 1].pref);
  aint[node].sum = aint[2 * node].sum + aint[2 * node + 1].sum;
  aint[node].pref = max(aint[2 * node].pref, aint[2 * node].sum + aint[2 * node + 1].pref);
  aint[node].suf = max(aint[2 * node + 1].suf, aint[2 * node + 1].sum + aint[2 * node].suf);
}

void query(long long node, long long st, long long dr, long long a, long long b) {
  if (a <= st && dr <= b) {
    ans1 = max(ans1, max(ans2 + aint[node].pref, aint[node].ssm));
    ans2 = max(0LL, max(aint[node].suf, ans2 + aint[node].sum));
    return ;
  }
  long long med = (st + dr) / 2;
  if (a <= med)
    query(2 * node, st, med, a, b);
  if (med < b)
    query(2 * node + 1, med + 1, dr, a, b);
}

int main() {
  freopen("sequencequery.in", "r", stdin);
  freopen("sequencequery.out", "w", stdout);

  long long n, m;
  scanf("%lld%lld", &n, &m);
  for (long long i = 1; i <= n; ++i) {
    long long x;
    scanf("%lld", &x);
    update(1, 1, n, i, x);
  }

  for (long long i = 1; i <= m; ++i) {
    long long x, y;
    scanf("%lld%lld", &x, &y);
    ans1 = -1000000000000;
    ans2 = 0;
    query(1, 1, n, x, y);
    printf("%lld\n", ans1);
  }

  return 0;
}