using namespace std;
#ifdef EZ
   #include "./ez/ez.h"
   const string FILE_NAME = "test";
#else
   #include <bits/stdc++.h>
   const string FILE_NAME = "sequencequery";
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define fi first
#define se second
#define cin fin
#define cout fout
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");

const int nMAX = 100e3;

int n, q;
int v[nMAX + 1];
struct Nod {
   ll stmax = LLONG_MIN>>1, max = LLONG_MIN>>1, drmax = LLONG_MIN>>1;
   ll fullsum;
} aint[4*nMAX + 1];


void buildAint(int nod = 1, int st = 1, int dr = n)
{
   if (st == dr)
      return (void) (aint[nod] = {v[st], v[st], v[st], v[st]});
   
   int mj = st+dr >> 1;
   buildAint(nod<<1, st, mj);
   buildAint(nod<<1|1, mj+1, dr);

   aint[nod] = {
      max(aint[nod<<1].stmax, aint[nod<<1].fullsum + aint[nod<<1|1].stmax),
      max({aint[nod<<1].max, aint[nod<<1|1].max, aint[nod<<1].drmax + aint[nod<<1|1].stmax}),
      max(aint[nod<<1|1].drmax, aint[nod<<1|1].fullsum + aint[nod<<1].drmax),
      aint[nod<<1].fullsum + aint[nod<<1|1].fullsum
   };
}


Nod queryAint(int qst, int qdr, int nod = 1, int st = 1, int dr = n)
{
   if (qdr < st || dr < qst)
      return {LLONG_MIN>>1, LLONG_MIN>>1, LLONG_MIN>>1, 0};
   if (qst <= st && dr <= qdr)
      return aint[nod];
   
   int mj = st+dr >> 1;
   Nod q1 = queryAint(qst, qdr, nod<<1, st, mj);
   Nod q2 = queryAint(qst, qdr, nod<<1|1, mj+1, dr);
   
   Nod x = {
      max(q1.stmax, q1.fullsum + q2.stmax),
      max({q1.max, q2.max, q1.drmax + q2.stmax}),
      max(q2.drmax, q2.fullsum + q1.drmax),
      q1.fullsum + q2.fullsum
   };
   cerr << st << ' ' << dr << ' ' << x.stmax << ' ' << x.max << ' ' << x.drmax << ' ' << x.fullsum << '\n';
   return x;
}


int main()
{
   cin >> n >> q;
   for (int i = 1; i <= n; ++i)
      cin >> v[i];
   
   buildAint();

   while (q--)
   {
      int x, y;
      cin >> x >> y;
      cout << queryAint(x, y).max << '\n';
   }
}