#include <fstream>
#include <algorithm>
 
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 array[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 = array[left];
    segment_tree[node].pref_scmax = array[left];
    segment_tree[node].suff_scmax = array[left];
    segment_tree[node].scmax = array[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[])
{
  std::ifstream in("sequencequery.in");
  std::ofstream out("sequencequery.out");
  
  int n, q; 
  in >> n >> q;
 
  for (int i = 1; i <= n; ++i)
    in >> array[i];
 
  build(1, 1, n);
 
  while (q--) {
    int left, right;
    in >> left >> right;
    out << query(1, 1, n, left, right).scmax << "\n";
  }
 
  return 0;
}