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

#define aintSize 131072
#define Nadejde 100000
#define NIL -1

typedef struct {
  int sum;
  int prefix;
  int suffix;
  int best;
} cell;

int N, M;
cell tree[2 * aintSize + 1];

int max;  // solutia ceruta.
int curr; // subsecventa de suma maxima terminata in capatul intervalului curent!

/** max(X, Y). **/
int MAX(int X, int Y) {
  return X > Y ? X : Y;
}

/** Construieste tatal din cei 2 fii ai sai. **/
void look(cell *u, cell *l, cell *r) {
  u -> sum = l -> sum + r -> sum;
  u -> prefix = MAX(l -> prefix, l -> sum + r -> prefix);
  u -> suffix = MAX(r -> suffix, r -> sum + l -> suffix);
  u -> best = MAX(MAX(l -> best, r -> best), l -> suffix + r -> prefix);
}

/** Actualizeaza nodul "u". **/
void update(int u, int left, int right, int pos, int val) {
  /* Caz limita. */
  if (left == right) {
    tree[u].sum = val;
    tree[u].prefix = val;
    tree[u].suffix = val;
    tree[u].best = val;
    return;
  }

  /* Recursivitate. */
  int mid = (left + right) >> 1;

  if (pos <= mid) {
    update(2 * u, left, mid, pos, val);
  } else {
    update(2 * u + 1, mid + 1, right, pos, val);
  }

  /* Intoarce-te din recursivitate si actualizeaza. */
  look(&tree[u], &tree[2 * u], &tree[2 * u + 1]);
}

/** Vezi daca poti imbunatati maximul. **/
void refresh(int x) {
  max = MAX(max, x);
}

/** Raspunde pentru intervalul [a, b]. **/
void query(int u, int left, int right, int a, int b) {
  /* Cazuri limita. */
  if (a <= left && right <= b) {
    refresh(tree[u].best);
    refresh(curr + tree[u].prefix);
    curr = MAX(curr + tree[u].sum, tree[u].suffix);
    refresh(curr);
    return;
  }

  /* Recursivitate. */
  int mid = (left + right) >> 1;

  if (a <= mid) {
    query(2 * u, left, mid, a, b);
  }
  if (b > mid) {
    query(2 * u + 1, mid + 1, right, a, b);
  }
}

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

  /* Citirea datelor. */
  fscanf(f, "%d %d", &N, &M);
  for (i = 1; i <= N; i++) {
    fscanf(f, "%d", &val);
    update(1, 1, N, i, val);
  }

  /* Raspunde la intrebari. */
  for (i = 1; i <= M; i++) {
    fscanf(f, "%d %d", &a, &b);

    curr = 0;
    max = INT_MIN;
    query(1, 1, N, a, b);
    fprintf(stdout, "%d\n", max);
  }
  fclose(f);
  fclose(stdout);

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