#include <bits/stdc++.h>

using namespace std;

ifstream in("sequencequery.in");
ofstream out("sequencequery.out");

using ll = long long;

const ll inf = (ll)1e14;
const int maxN = (int)1e5 + 5;

struct Node {
  ll sum, maxSum, pref, suf;
  Node(ll val) {
    sum = maxSum = pref = suf = val;
  }
  Node() {}
};

int n, m;

int v[maxN];

Node tree[4 * maxN];

Node combine(Node a, Node b) {
  Node ans;
  ans.sum = a.sum + b.sum;
  ans.pref = max(a.pref, a.sum + b.pref);
  ans.suf = max(b.suf, b.sum + a.suf);
  ans.maxSum = max(max(a.maxSum, b.maxSum), a.suf + b.pref);
  return ans;
}

void build(int u, int l, int r) {
  if (l == r) {
    tree[u] = Node(v[l]);
    return;
  }
  int m = (l + r) / 2;
  build(2 * u, l, m);
  build(2 * u + 1, m + 1, r);
  tree[u] = combine(tree[2 * u], tree[2 * u + 1]);
}

Node query(int u, int l, int r, int ql, int qr) {
  if (ql > qr) {
    return Node(-inf);
  }
  if (ql == l && qr == r) {
    return tree[u];
  }
  int m = (l + r) / 2;
  return combine(query(2 * u, l, m, ql, min(qr, m)),
                 query(2 * u + 1, m + 1, r, max(ql, m + 1), qr));
}

int main() {
  in >> n >> m;
  for (int i = 1; i <= n; i++) {
    in >> i[v];
  }
  build(1, 1, n);
  for (int i = 1; i <= m; i++) {
    int l, r;
    in >> l >> r;

    out << query(1, 1, n, l, r).maxSum << "\n";
  }
  return 0;
}