#include <cstdio>
#include <algorithm>
using namespace std;
 
const int MAXN = 100005;
const int INF = 0x3f3f3f3f;

int n, m, a[MAXN];
int result, lastsuf;
 
struct {
  int suma, pref, suf, best;
  void init(int k) {
    suma = pref = suf = best = a[k];
  }
}tree[4 * MAXN];
 
#define left(x) (x << 1)
#define right(x) ((x << 1) + 1)

#define max3(x, y, z) (max(max((x), (y)), (z)))
 
void read() {
  scanf("%d %d ", &n, &m);
  for (int i = 1; i <= n; i++)
    scanf("%d ", &a[i]);
}
 
void build(int st = 1, int dr = n, int node = 1) {
  if (st == dr) {
    tree[node].init(st);
    return;
  }
 
  int mid = (st + dr) >> 1;
 
  build(st, mid, left(node));
  build(mid + 1, dr, right(node));
 
  tree[node].suma = tree[left(node)].suma + tree[right(node)].suma;
  tree[node].pref = max(tree[left(node)].pref, tree[left(node)].suma + tree[right(node)].pref);
  tree[node].suf = max(tree[right(node)].suf, tree[right(node)].suma + tree[left(node)].suf);
  tree[node].best = max3(tree[left(node)].best, tree[right(node)].best, tree[left(node)].suf + tree[right(node)].pref);
}
 
void query(int qst, int qdr, int st = 1, int dr = n, int node = 1) {
  if (qst <= st && qdr >= dr) {
    result = max3(result, tree[node].best, lastsuf + tree[node].pref);
    lastsuf = max(lastsuf + tree[node].suma, tree[node].suf);
    return;
  }
 
  if(st >= dr)
      return;
 
  int mid = (st + dr) >> 1;
 
  if (qst <= mid)
    query(qst, qdr, st, mid, left(node));
  if (dr > mid)
    query(qst, qdr, mid + 1, dr, right(node));
}
 
void solve() {
  int a, b;
  for (int i = 1; i <= m; i++) {
    scanf("%d %d ", &a, &b);
    result = lastsuf = -INF;
    query(a, b);
    printf("%d\n", result);
  }
}

int main() {
  freopen("sequencequery.in", "r", stdin);
  freopen("sequencequery.out", "w", stdout);
 
  read();
  build();
  solve();
 
  return 0;
}