#include <climits>
#include <stdio.h>

#define MAXN 100001
#define MAXP 200001

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int n, p;
int v[MAXN];

struct segtree {
private:
  struct node {
    int sum;
    int max;
    int st;
    int dr;

    const node operator+(const node &other) const {
      node result = {INT_MIN, INT_MIN, INT_MIN, INT_MIN};

      result.sum = this->sum + other.sum;
      result.st = MAX(this->st, this->sum + other.st);
      result.dr = MAX(other.dr, this->dr + other.sum);
      result.max = MAX(this->dr + other.st, MAX(this->max, other.max));

      return result;
    }
  };

  int n;
  node aint[4 * MAXN];

  void build(int node, int s, int d) {
    if (s == d)
      aint[node] = {v[s], v[s], v[s], v[s]};
    else {
      int m = (s + d) / 2;
      build(node * 2, s, m);
      build(node * 2 + 1, m + 1, d);

      aint[node] = aint[node * 2] + aint[node * 2 + 1];
    }
  }

  node query(int node, int s, int d, int a, int b) {
    if (a <= s && d <= b) {
      return aint[node];
    }
    struct node st = {INT_MIN, INT_MIN, INT_MIN, INT_MIN};
    struct node dr = {INT_MIN, INT_MIN, INT_MIN, INT_MIN};
    int m = (s + d) / 2;
    if (b <= m)
      return query(node * 2, s, m, a, b);
    if (a > m)
      return query(node * 2 + 1, m + 1, d, a, b);

    st = query(node * 2, s, m, a, b);
    dr = query(node * 2 + 1, m + 1, d, a, b);
    return st + dr;
  }

public:
  void build() { build(1, 0, n - 1); }
  int query(int a, int b) { return query(1, 0, n - 1, a, b).max; }
  void init(int n) { this->n = n; }
};

segtree aint;

int main() {
  freopen("sequencequery.in", "r", stdin);
  freopen("sequencequery.out", "w", stdout);
  scanf("%d%d", &n, &p);
  for (int i = 0; i < n; i++) {
    scanf("%d", &v[i]);
  }
  aint.init(n);
  aint.build();

  for (int i = 0; i < p; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    printf("%d\n", aint.query(a, b));
  }
  return 0;
}