#include <iostream>

auto *in = fopen("sequencequery.in", "r"), *out = fopen("sequencequery.out", "w") ;

const int maxn = 1e5 ;

using i64 = long long ;

int v[1 + maxn] ;

struct DC {
    i64 totalSum ;
    i64 prefixSum, suffixSum ;
    i64 bestSum ;
};

DC aint[(maxn << 2) + 1] ;

DC join(DC left, DC right) {
  DC ret ;
  ret.totalSum = left.totalSum + right.totalSum ;
  ret.prefixSum = std::max(left.prefixSum, left.totalSum + right.prefixSum) ;
  ret.suffixSum = std::max(left.suffixSum + right.totalSum, right.suffixSum) ;
  ret.bestSum = std::max({left.bestSum, right.bestSum, left.suffixSum + right.prefixSum}) ;
  return ret ;
}

void build(int node, int left, int right) {
  if (left == right) {
    aint[node] = {v[left], v[left], v[left], v[left]} ;
    return;
  }
  int mid = ((left + right) >> 1) ;
  build(node << 1, left, mid) ;
  build((node << 1) + 1, mid + 1, right) ;
  aint[node] = join(aint[node << 1], aint[(node << 1) + 1]) ;
}

DC query(int node, int leftInt, int rightInt, int left, int right) {
  if (leftInt == left && rightInt == right) {
    return aint[node] ;
  }
  int mid = ((leftInt + rightInt) >> 1) ;
  if (right <= mid) {
    return query(node << 1, leftInt, mid, left, right) ;
  }
  if (mid < left) {
    return query((node << 1) + 1, mid + 1, rightInt, left, right) ;
  }
  DC possibleLeft = query(node << 1, leftInt, mid, left, mid) ;
  DC possibleRight = query((node << 1) + 1, mid + 1, rightInt, mid + 1, right) ;
  DC ret = join(possibleLeft, possibleRight) ;
  return ret ;
}

int main() {
  int n, querys ;
  fscanf(in, "%d %d\n", &n, &querys) ;
  for (int i = 1 ; i <= n ; ++ i) {
    fscanf(in, "%d ", v + i) ;
  }
  build(1, 1, n) ;
  int left, right ;
  for (int i = 1 ; i <= querys ; ++ i) {
    fscanf(in, "%d %d\n", &left, &right) ;
    i64 answer = query(1, 1, n, left, right).bestSum ;
    fprintf(out, "%lld\n", answer) ;
  }
}