#include <bits/stdc++.h>

using namespace std;

const int N = 100000;

struct tree_node
{
  long long sum; // suma subsecventei
  long long pref_scmax; // prefixul de suma maxim
  long long suff_scmax; // sufixul de suma maxima
  long long scmax; // subsecventa de suma maxima
};

int a[N + 1];
tree_node segment_tree[N * 4 + 1];

tree_node update_node(tree_node left_node, tree_node right_node)
{
  tree_node current_node;

  current_node.sum =
      left_node.sum + right_node.sum;

  current_node.pref_scmax =
      std::max(left_node.pref_scmax,
               left_node.sum + right_node.pref_scmax);

  current_node.suff_scmax =
      std::max(right_node.suff_scmax,
               right_node.sum + left_node.suff_scmax);

  current_node.scmax =
      std::max(left_node.suff_scmax + right_node.pref_scmax,
               std::max(left_node.scmax, right_node.scmax));

  return current_node;
}

void build(int node, int left, int right)
{
  if (left == right)
  {
    segment_tree[node].sum = a[left];
    segment_tree[node].pref_scmax = a[left];
    segment_tree[node].suff_scmax = a[left];
    segment_tree[node].scmax = a[left];
  }
  else
  {
    int middle = (left + right) / 2;
    build(node * 2, left, middle);
    build(node * 2 + 1, middle + 1, right);

    segment_tree[node] = update_node(segment_tree[node * 2], segment_tree[node * 2 + 1]);
  }
}

tree_node query(int node, int left, int right, int query_left, int query_right)
{
  if (query_left <= left and right <= query_right)
    return segment_tree[node];
  else
  {
    int middle = (left + right) / 2;

    if (query_right <= middle)
      return query(node * 2, left, middle, query_left, query_right);
    if (middle + 1 <= query_left)
      return query(node * 2 + 1, middle + 1, right, query_left, query_right);

    tree_node left_node = query(node * 2, left, middle, query_left, query_right),
              right_node = query(node * 2 + 1, middle + 1, right, query_left, query_right);

    return update_node(left_node, right_node);
  }
}

int main(int argc, const char *argv[])
{
  ifstream fin("sequencequery.in");
  ofstream fout("sequencequery.out");
  int n, q;
  fin >> n >> q;

  for (int i = 1; i <= n; i++)
    fin >> a[i];

  build(1, 1, n);

  while (q--)
  {
    int left, right;
    fin >> left >> right;
    fout << query(1, 1, n, left, right).scmax << "\n";
  }
  return 0;
}