#include <fstream>
using namespace std;

typedef struct
{
  int start, end;   // inclusive indices
  int min;          // minimum of partial sum in [start - 1, end - 1]
  int max;          // maximum of partial sum in [start, end]
  int maxSeq;       // maximum sequence of this interval
} Interval;


const int MAXINT = 2 * 100000 - 1;
Interval T[MAXINT + 1];

ifstream in("sequencequery.in");


void buildTree(int ind, int intStart, int intEnd);
void combineIntervals(Interval &dest, Interval &left, Interval &right);
void queryTree(Interval &dest, int ind, int intStart, int intEnd);


int main(int argc, char *argv[])
{
  int n, m;

  in >> n >> m;
  buildTree(1, 1, n);

  ofstream out("sequencequery.out");
  Interval answer;
  for(int count = 1, x, y; count <= m; ++count)
  {
    in >> x >> y;
    queryTree(answer, 1, x, y);
    out << answer.maxSeq << endl;
  }

  return 0;
}

void buildTree(int ind, int intStart, int intEnd)
{
  static int partialSum;  // current value of the partial sum
  static int x;           // work variable

  if(intStart == intEnd)
  {
    T[ind].start = T[ind].end = intStart;
    T[ind].min = partialSum;

    in >> x;
    T[ind].max = partialSum += x;
    T[ind].maxSeq = T[ind].max - T[ind].min;
    return;
  }

  // intStart, intEnd <= 100000; it's safe to add them
  const int mid = (intStart + intEnd) / 2;
  const int leftInd = ind * 2;
  const int rightInd = leftInd + 1;
  buildTree(leftInd, intStart, mid);
  buildTree(rightInd, mid + 1, intEnd);
  combineIntervals(T[ind], T[leftInd], T[rightInd]);
}

void queryTree(Interval &dest, int ind, int intStart, int intEnd)
{
  if(T[ind].start == intStart && T[ind].end == intEnd)
  {
    dest = T[ind];
    return;
  }

  // if the query overlaps with the interval of left subtree
  const int leftInd = ind * 2;
  const int rightInd = leftInd + 1;
  if(intStart <= T[leftInd].end && intEnd >= T[leftInd].start)
  {
    // the query is contained by the interval of left subtree
    if(intEnd <= T[leftInd].end)
    {
      queryTree(dest, leftInd, intStart, intEnd);
      return;
    }

    queryTree(dest, leftInd, intStart, T[leftInd].end);
    Interval aux;
    queryTree(aux, rightInd, T[leftInd].end + 1, intEnd);
    combineIntervals(dest, dest, aux);
    return;
  }

  // the query is contained by the interval of right subtree
  queryTree(dest, rightInd, intStart, intEnd);
  return;
}

void combineIntervals(Interval &dest, Interval &left, Interval &right)
{
  dest.start = left.start;
  dest.end = right.end;
  dest.min = min(left.min, right.min);
  dest.max = max(left.max, right.max);
  dest.maxSeq = max(left.maxSeq, max(right.maxSeq, right.max - left.min));
}