// Arbori de intervale

#include <stdio.h>

#define int64 long long

inline int64 max(int64 a, int64 b) { return a > b ? a : b; }
inline int64 max(int64 a, int64 b, int64 c) { return max(a, max(b, c)); }

#define MAX_N 100000

struct Node {
  int64 totalSum, maxSum;
  int64 leftSum, rightSum;

  Node() {}
  Node(const int64& value) {
    totalSum = maxSum = leftSum = rightSum = value;
  }
};

int v[MAX_N];

Node aint[MAX_N * 2];

Node combine(const Node& left, const Node& right) {
  Node node;

  node.totalSum = left.totalSum + right.totalSum;

  node.maxSum = max(left.maxSum, right.maxSum, left.rightSum + right.leftSum);

  node.leftSum = max(left.leftSum, left.totalSum + right.leftSum);
  node.rightSum = max(right.rightSum, left.rightSum + right.totalSum);

  return node;
}

void build(int node, int nLeft, int nRight) {
  if (nLeft == nRight) {
    aint[node] = v[nLeft];
    return;
  }

  int nMid, leftSon, rightSon;

  nMid = (nLeft + nRight) / 2;
  leftSon = node + 1;
  rightSon = node + 2 * (nMid - nLeft + 1);

  build(leftSon, nLeft, nMid);
  build(rightSon, nMid + 1, nRight);

  aint[node] = combine(aint[leftSon], aint[rightSon]);
}

Node query(int node, int nLeft, int nRight, int qLeft, int qRight) {
  if (qLeft <= nLeft && qRight >= nRight)
    return aint[node];

  int nMid, leftSon, rightSon;
  Node result;

  nMid = (nLeft + nRight) / 2;
  leftSon = node + 1;
  rightSon = node + 2 * (nMid - nLeft + 1);

  if (qLeft <= nMid && qRight > nMid)
    result = combine(query(leftSon, nLeft, nMid, qLeft, qRight), query(rightSon, nMid + 1, nRight, qLeft, qRight));
  else if (qLeft <= nMid)
    result = query(leftSon, nLeft, nMid, qLeft, qRight);
  else
    result = query(rightSon, nMid + 1, nRight, qLeft, qRight);

  return result;
}

int main() {
  FILE *fin, *fout;
  fin = fopen("sequencequery.in", "r");
  fout = fopen("sequencequery.out", "w");

  int n, m, i, a, b;

  fscanf(fin, "%d%d", &n, &m);
  for (i = 0; i < n; ++i)
    fscanf(fin, "%d", &v[i]);

  build(0, 0, n - 1);

  while (m--) {
    fscanf(fin, "%d%d", &a, &b);
    fprintf(fout, "%lld\n", query(0, 0, n - 1, a - 1, b - 1).maxSum);
  }

  fclose(fin);
  fclose(fout);
  return 0;
}