#include <bits/stdc++.h>

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

struct node {
  long long sum_max, sum_max_stanga, sum_max_dreapta, suma_totala;
};
node aint[800007];
node ans1, ans2;
long long n, q, v[200007];

node combine(node a, node b)
{
    node af;
    af.suma_totala = a.suma_totala + b.suma_totala;
    af.sum_max_stanga = max(a.sum_max_stanga, a.suma_totala + b.sum_max_stanga);
    af.sum_max_dreapta = max(b.sum_max_dreapta,b.suma_totala+ a.sum_max_dreapta);
    af.sum_max = max(max(a.sum_max,b.sum_max),max(max(af.sum_max_stanga,af.sum_max_dreapta),a.sum_max_dreapta + b.sum_max_stanga));
    return af;
}

void build (long long nod, long long stanga, long long dreapta) {
  if (stanga == dreapta) {
    aint[nod].sum_max = v[stanga];
    aint[nod].sum_max_stanga = v[stanga];
    aint[nod].sum_max_dreapta = v[stanga];
    aint[nod].suma_totala = v[stanga];

    return;
  }

  long long mijloc = (stanga + dreapta) / 2;
  build(2 * nod, stanga, mijloc);
  build(2 * nod + 1, mijloc + 1, dreapta);

  aint[nod] = combine(aint[2 * nod], aint[2 * nod + 1]);
}

void update (long long nod, long long stanga, long long dreapta, long long poz) {
  if (stanga == dreapta) {
    aint[nod].sum_max = v[poz];
    aint[nod].sum_max_stanga = v[poz];
    aint[nod].sum_max_dreapta = v[poz];
    aint[nod].suma_totala = v[poz];

    return;
  }

  long long mijloc = (stanga + dreapta) / 2;
  if (poz <= mijloc) {
    update(2 * nod, stanga, mijloc, poz);
  } else {
    update(2 * nod + 1, mijloc + 1, dreapta, poz);
  }

  aint[nod] = combine(aint[2 * nod], aint[2 * nod + 1]);
}

void query (long long nod, long long stanga, long long dreapta, long long a, long long b) {
  if (a <= stanga && dreapta <= b) {
    ans1 = combine(ans1, aint[nod]);

    return;
  }

  long long mijloc = (stanga + dreapta) / 2;
  if (a <= mijloc) {
    query(2 * nod, stanga, mijloc, a, b);
  }

  if (b > mijloc) {
    query(2 * nod + 1, mijloc + 1, dreapta, a, b);
  }
}

int main () {

  fin >> n >> q;

  for (int i = 1; i <= n; i++) {
    fin >> v[i];
  }

  build(1, 1, n);


  while (q) {
    long long c, a, b;

    /*
    if (c == 0) {
      fin >> a >> b;

      a++;
      v[a] = b;
      update(1, 1, n, a);
    } else
    */{
      fin >> a >> b;

      ans1.suma_totala = ans1.sum_max = ans1.sum_max_stanga = ans1.sum_max_dreapta = -999999999;

      query(1, 1, n, a, b);

      fout << ans1.sum_max << '\n';
    }

    q--;
  }

  return 0;
}