#include <iostream>
#include <fstream>

using namespace std;

typedef long long ll;

const int NMAX = 1e5;
const long long INF = (1LL << 60);

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

struct Node {
  ll best;
  ll maxleft;
  ll maxright;
  ll total;
};

int v[1 + NMAX];
ll res, tot;
Node arb[1 + 4 * NMAX];

void computenode(int node, int from, int to) {
  Node &a = arb[2 * node];
  Node &b = arb[2 * node + 1];

  arb[node].best = max(a.maxright + b.maxleft, max(a.best, b.best));
  arb[node].maxleft = max(a.maxleft, a.total + b.maxleft);
  arb[node].maxright = max(b.maxright, a.maxright + b.total);
  arb[node].total = a.total + b.total;
}

void buildtree(int node, int from, int to) {
  if(from == to) {
    arb[node] = {v[from], v[from], v[from], v[from]};
  } else {
    int mid = (from + to) / 2;

    buildtree(2 * node, from, mid);
    buildtree(2 * node + 1, mid + 1, to);

    computenode(node, from, to);
  }
}

void query(int node, int from, int to, int x, int y) {
  if(x <= from && to <= y) {
    res = max(res, arb[node].best);
    res = max(res, tot + arb[node].maxleft);
    tot = max(tot + arb[node].total, arb[node].maxright);
  } else {
    int mid = (from + to) / 2;
    if(x <= mid)
      query(2 * node, from, mid, x, y);
    if(mid + 1 <= y)
      query(2 * node + 1, mid + 1, to, x, y);
  }
}

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

  buildtree(1, 1, n);
  for(int i = 1; i <= m; i++) {
    int x, y;
    in >> x >> y;
    res = -INF;
    tot = 0;
    query(1, 1, n, x, y);
    out << res << '\n';
  }

  in.close();
  out.close();
  return 0;
}