#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int INF = 0x3f3f3f3f;

struct {
  int suma, pref, suf, best;
}tree[4 * MAXN];

int n, m, a[MAXN];

#define left(x) ((x) << 2)
#define right(x) (((x) << 2) + 1)

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].suma = tree[node].pref = tree[node].suf = tree[node].best = a[st];
    return;
  }

  int mid = (st + dr) / 2;

  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 = max(tree[left(node)].best, tree[right(node)].best);
  tree[node].best = max(tree[node].best, tree[left(node)].suf + tree[right(node)].pref);
}

int result, lastsuf;

void query(int qst, int qdr, int st = 1, int dr = n, int node = 1) {
  if (qst <= st && qdr >= dr) {
    result = max(result, tree[node].best);
    result = max(result, lastsuf + tree[node].pref);
    lastsuf = max(lastsuf + tree[node].suma, tree[node].suf);
    return;
  }

  if(st >= dr)
      return;

  int mid = (st + dr) / 2;

  if (qst <= mid)
    query(qst, qdr, st, mid, left(node));
  if (dr > mid)
    query(qst, qdr, mid + 1, dr, right(node));
}

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

  read();
  build();

  for (int i = 1; i <= m; i++) {
    int a, b;
    scanf("%d %d ", &a, &b);
    a = min(a, b);
    b = max(a, b);
    result = lastsuf = -INF;
    query(a, b);
    printf("%d\n", result);
  }

  return 0;
}