#include <bits/stdc++.h>

using namespace std;

struct Node {
  long long ssm, sum, pref, suff;
}aint[400005];

Node join(Node a, Node b) {
  Node ans;
  ans.ssm = max(max(a.ssm, b.ssm), a.suff + b.pref);
  ans.sum = a.sum + b.sum;
  ans.pref = max(a.pref, a.sum + b.pref);
  ans.suff = max(b.suff, b.sum + a.suff);
  return ans;
}

void update(int node, int l, int r, int pos, int val) {
  if (l == r) {
    aint[node] = {val, val, val, val};
    return ;
  }
  int mid = (l + r) / 2;
  if (pos <= mid)
    update(2 * node, l, mid, pos, val);
  else
    update(2 * node + 1, mid + 1, r, pos, val);
  aint[node] = join(aint[2 * node], aint[2 * node + 1]);
}

Node query(int node, int l, int r, int a, int b) {
  if (a > b)
    return {0, 0, 0, 0};
  if (a <= l && r <= b)
    return aint[node];
  int mid = (l + r) / 2;
  Node s1, s2;
  bool x = 0, y = 0;
  if (a <= mid)
    x = 1, s1 = query(2 * node, l, mid, a, b);
  if (mid < b)
    y = 1, s2 = query(2 * node + 1, mid + 1, r, a, b);
  if (x == 0)
    return s2;
  if (y == 0)
    return s1;
  return join(s1, s2);
}

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

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

  for (int i = 1; i <= m; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    printf("%lld\n", query(1, 1, n, x, y).ssm);
  }

  return 0;
}