#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long LL;

struct nod
{
      LL sum;
      LL pref;
      LL suf;
      LL best;
      nod(){
            upd(-1<<25);
      }
      void upd(const int &val){

            sum = val;
            pref = val;
            suf = val;
            best = val;
      }
      void upd(const nod &left,const nod &right)
      {
            sum = left.sum + right.sum;
            pref = max(left.pref,left.sum+right.pref);
            suf = max(right.suf,left.suf+right.sum);
            best = max(right.best,left.best);
            best = max(best,right.pref+left.suf);
      }
};

nod AINT[1<<19];

void update(int care,int st,int dr,const int &poz,const int & val)
{
      if(st == dr)
      {
            AINT[care].upd(val);
            return ;
      }
      int mid = (st+dr)>>1;
      if(poz <= mid)
            update(care*2,st,mid,poz,val);
      else
            update(care*2+1,mid+1,dr,poz,val);
      AINT[care].upd(AINT[care*2],AINT[care*2+1]);
}

nod query(int care,int st,int dr,const int &lo,const int &hi)
{
      if(lo <= st && dr <= hi)
            return AINT[care];
      int mid = (st+dr)/2;
      nod l,r;
      if(lo <= mid)
            l = query(care*2,st,mid,lo,hi);
      if(mid < hi)
            r = query(care*2+1,mid+1,dr,lo,hi);
      nod ret;
      ret.upd(l,r);
      return ret;
}

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

      int n,m,i,x,y,tip;
      long long dat;
      scanf("%d %d\n",&n,&m);
      for(i=1;i<=n;++i)
      {
            scanf("%d",&x);
            update(1,1,n,i,x);
      }
      while(m--)
      {
            scanf("%d %d",&x,&y);
            printf("%lld\n",  query(1,1,n,x,y).best);
      }
}