#include <stdio.h>
#include <limits.h>

#define Nadejde 100000
#define NIL -1

int N, M;
int val[Nadejde + 1];

int MAX(int X, int Y) {
  return X > Y ? X : Y;
}

int ssm(int a, int b) {
  int i, max = INT_MIN, best = NIL;

  for (i = a; i <= b; i++) {
    best = val[i] + MAX(0, best);
    max = MAX(max, best);
  }
  return max;
}

int main(void) {
  int i, a, b;
  FILE *f = fopen("sequencequery.in", "r");
  freopen("sequencequery.out", "w", stdout);

  fscanf(f, "%d %d", &N, &M);
  for (i = 1; i <= N; i++) {
    fscanf(f, "%d", &val[i]);
  }
  for (i = 1; i <= M; i++) {
    fscanf(f, "%d %d", &a, &b);
    fprintf(stdout, "%d\n", ssm(a, b));
  }
  fclose(f);
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}