#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long int64;
const int maxN = 262144;

class Node {
public:
  int64 ssmax, pref, suf, sum;
  Node(int64 _ssmax = 0, int64 _pref = 0, int64 _suf = 0, int64 _sum = 0):
    ssmax(_ssmax), pref(_pref), suf(_suf), sum(_sum) { }
} arb[maxN << 1];

int64 v[maxN];

void build(int64 nod, int64 st, int64 dr) {
  if(st == dr) {
    int64 mx = v[st];
    arb[nod] = Node(mx, mx, mx, v[st]);
  } else {
    int64 mid = (st + dr) >> 1, k = nod << 1;
    build(k, st, mid);
    build(k + 1, mid + 1, dr);
    arb[nod].sum = arb[k].sum + arb[k + 1].sum;
    arb[nod].pref = max(arb[k].pref, arb[k + 1].pref + arb[k].sum);
    arb[nod].suf = max(arb[k].suf + arb[k + 1].sum, arb[k + 1].suf);
    arb[nod].ssmax = max(max(arb[k].ssmax, arb[k + 1].ssmax), arb[k].suf + arb[k + 1].pref);
  }
}

void query(int64 nod, int64 x, int64 y, int64 st, int64 dr, int64& s, int64& ans) {
  if(x <= st and dr <= y) {
    ans = max(ans, max(s + arb[nod].pref, arb[nod].ssmax));
    s = max(s + arb[nod].sum, arb[nod].suf);
  } else {
    int64 mid = (st + dr) >> 1, k = nod << 1;
    if(x <= mid)
      query(k, x, y, st, mid, s, ans);
    if(y > mid)
      query(k + 1, x, y, mid + 1, dr, s, ans);
  }
}

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

  int64 N, M;

  scanf("%lld %lld\n", &N, &M);
  for(int i = 1; i <= N; ++ i)
    scanf("%lld", &v[i]);

  int64 p;
  for(p = 1; p < N; p <<= 1);
  build(1, 1, p);

  for(int64 i = 1; i <= M; ++ i) {
    int64 a, b;
    scanf("%lld %lld", &a, &b);
    int64 s, ans;
    s = ans = -(1LL << 60);
    query(1, a, b, 1, p, s, ans);
    printf("%lld\n", ans);
  }
  return 0;
}