#include <fstream>

using namespace std;

const int N_MAX = 1e5;
const int64_t INF = 1e18;

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

int N, M;
int a[N_MAX + 5];

struct { int64_t s, l, r, m; } st[4 * N_MAX + 5];

void Build(int node, int l, int r) {
   if (l == r) {
      st[node].s = a[l];
      st[node].l = a[l];
      st[node].r = a[l];
      st[node].m = a[l];
      return;
   }

   int m = (l + r) >> 1;
   int ls = node << 1, rs = ls | 1;

   Build(ls, l, m);
   Build(rs, m + 1, r);

   st[node].s = st[ls].s + st[rs].s;
   st[node].l = max(st[ls].l, st[ls].s + st[rs].l);
   st[node].r = max(st[rs].r, st[ls].r + st[rs].s);
   st[node].m = max(max(st[ls].m, st[rs].m), st[ls].r + st[rs].l);
}

void Query(int node, int l, int r, int ql, int qr, int64_t& best, int64_t& ans) {
   if (qr < l || r < ql)
      return;

   if (ql <= l && r <= qr) {
      ans = max(ans, max(st[node].m, best + st[node].l));
      best = max(best + st[node].s, st[node].r);
      return;
   }

   int m = (l + r) >> 1;
   int ls = node << 1, rs = ls | 1;

   Query(ls, l, m, ql, qr, best, ans);
   Query(rs, m + 1, r, ql, qr, best, ans);
}

int main() {
   fin >> N >> M;
   for (int i = 1; i <= N; ++i)
      fin >> a[i];

   Build(1, 1, N);

   while (M--) {
      int l, r;
      fin >> l >> r;

      int64_t best = -INF, ans = -INF;
      Query(1, 1, N, l, r, best, ans);

      fout << ans << "\n";
   }
   return 0;
}