#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

const ll inf = -1ll<<59;

struct nod {
   ll suma, best_suf, best_pref, best_sum;
   nod
   (ll suma = 0, ll best_suf = inf, ll best_pref = inf, ll best_sum = inf)
   : suma(suma), best_suf(best_suf), best_pref(best_pref), best_sum(best_sum) {};
};

nod operator + (const nod &a, const nod &b)
{
   nod aux;
   aux.suma = a.suma + b.suma;
   aux.best_suf = max(b.best_suf, b.suma + a.best_suf);
   aux.best_pref = max(a.best_pref, a.suma + b.best_pref);
   aux.best_sum = max({a.best_sum, b.best_sum, a.best_suf + b.best_pref});
   return aux;
}

int n, m, a[1 << 20];
nod aint[1 << 20];

void build(int l = 1, int r = n, int id = 1)
{
   if(l == r)
   {
      aint[id] = nod(a[l], a[l], a[l], a[l]);
      return;
   }

   int mij = (l + r) / 2;
   build(l, mij, id * 2);
   build(mij + 1, r, id * 2 + 1);
   aint[id] = aint[2 * id] + aint[2 * id + 1];
}

nod query(int x, int y, int l = 1, int r = n, int id = 1)
{
   if(l > y || x > r || l > r)
      return nod();
   if(l >= x && r <= y)
      return aint[id];
   if(l >= r)
      return nod();
   int mij = (l + r) / 2;
   return query(x, y, l, mij, id * 2) +
          query(x, y, mij + 1, r, id * 2 + 1);
}

int main()
{
   freopen("sequencequery.in", "r", stdin);
   freopen("sequencequery.out", "w", stdout);

   scanf("%d %d", &n, &m);
   for(int i = 1; i <= n; i++)
      scanf("%d", &a[i]);

   build();
   while (m--)
   {
      int x, y;
      scanf("%d %d", &x, &y);
      printf("%lld\n", query(x, y).best_sum);
   }

   return 0;
}