#include <iostream>
#include <fstream>

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

#define MAX(a , b) (((a) < (b)) ? (b) : (a))
#define MIN(a , b) (((a) < (b)) ? (a) : (b))

#define ll long long

int const nmax = 100000;
int const inf = -1000000000;

struct Node{
  ll result;
  ll sum;
  ll subleft;
  ll subright;
};

Node join(Node a , Node b){
  Node c;
  c.sum = a.sum + b.sum;
  c.subleft = MAX(a.subleft , a.sum + b.subleft);
  c.subright = MAX(b.subright , a.subright + b.sum);
  c.result = MAX(MAX(a.result , b.result) , MAX(c.subleft ,c.subright));
  return c;
}

Node aint[5 + 4 * nmax];
int v[5 + 4 * nmax];

void build(int node , int from , int to){
  if(from < to){
    int mid = (from + to) / 2;
    build(node * 2 , from , mid);
    build(node * 2 + 1 , mid + 1 , to);
    aint[node] = join(aint[node * 2] , aint[node * 2 + 1]);
  } else
    aint[node] = {v[from] , v[from] , v[from] , v[from]};
}

Node query(int node , int from , int to , int x , int y){
  if(from == x && to == y){
    return aint[node];
  } else{
    Node result = {-inf , -inf , -inf , -inf};
    int mid = (from + to) / 2;
    if(x <= mid){
      result = query(node * 2 , from , mid , x , MIN(y , mid));
    }
    if(mid < y){
      if(result.result == -inf){
        result = query(node * 2 + 1, mid + 1 ,to , MAX(x , mid + 1) , y);
      } else
        result = join(result , query(node * 2 + 1, mid + 1 ,to , MAX(x , mid + 1) , y) );
    }
    return result;
  }
}

int main()
{
  int n , m;
  in >> n >> m;
  for(int i = 1 ; i <= n ;i++)
    in >> v[i];
  build(1 , 1 , n);
  for(int i = 1 ; i <= m ;i++){
    int x , y;
    in >> x >> y;
    Node result;
    result = query(1 , 1 , n , x , y);
    out << result.result << '\n';
  }
  return 0;
}