#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int y[100001];
struct D{
int a, s, r, pref, suf;
}x[400001];

D C(D a, D b)
{D c;
 c.s=a.s+b.s;
 c.pref=max(a.pref, a.s+b.pref);
 c.suf=max(b.suf, b.s+a.suf);
 c.r=max(a.suf+b.pref, max(a.r, b.r));

 return c;
}

void Build(int nod, int st, int dr)
{if(st==dr)
 x[nod].r=x[nod].s=x[nod].pref=x[nod].suf=y[st];
 else
 {int mij=(st+dr)/2;

  Build(nod*2, st, mij);
  Build(nod*2+1, mij+1, dr);

  x[nod]=C(x[nod*2], x[nod*2+1]);
 }
}

D Query(int nod, int st, int dr, int qs, int qd)
{if(st>=qs && dr<=qd)
 return x[nod];
 else
 {int mij=(st+dr)/2;

  if(mij>=qd)return Query(nod*2, st, mij, qs, qd);
  else if(mij<qs)return Query(nod*2+1, mij+1, dr, qs, qd);

  return C(Query(nod*2, st, mij, qs, qd), Query(nod*2+1, mij+1, dr, qs, qd));
 }
}

int main()
{   int n, m, a, b;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    fin>>y[i];

    Build(1, 1, n);
    //for(int i=1;i<=n*3;i++)cout<<x[i].r<<" ";

    for(int i=1;i<=m;i++)
    {fin>>a>>b;
     fout<<Query(1, 1, n, a, b).r<<"\n";
    }
    return 0;
}