#include<fstream>
#include<algorithm>
using namespace std;

typedef struct lol {
        int x,y,sum,rs;
}troll;

const int INF=0x3f3f3f3f;

int i,rs,q,sum,n,x,y,a[100005];
troll arb[400005];

void update(int left,int right,int nod) {
     if(left==right) arb[nod].x=arb[nod].y=arb[nod].sum=arb[nod].rs=a[right];
     else {
            int pivot=(left+right)/2;
            update(left,pivot,2*nod);
            update(pivot+1,right,2*nod+1);

            arb[nod].x=max(arb[2*nod].x,arb[2*nod].sum+arb[2*nod+1].x);
            arb[nod].y=max(arb[2*nod+1].y,arb[2*nod+1].sum+arb[2*nod].y);
            arb[nod].sum=arb[2*nod].sum+arb[2*nod+1].sum;
            arb[nod].rs=max(max(arb[2*nod].rs,arb[2*nod+1].rs),arb[2*nod].y+arb[2*nod+1].x);
          }
}

void query(int left,int right,int nod) {
     if(x<=left && right<=y)
     {
       rs=max(rs,max(sum+arb[nod].x,arb[nod].rs));
       sum=max(sum+arb[nod].sum,arb[nod].y);
     }
     else {
            int pivot=(left+right)/2;
            if(x<=pivot) query(left,pivot,2*nod);
            if(pivot<y) query(pivot+1,right,2*nod+1);
          }
}

int main()
{
  ifstream cin("sequencequery.in");
  ofstream cout("sequencequery.out");

  cin>>n>>q;
  for(i=1;i<=n;++i) cin>>a[i];

  update(1,n,1);

  while(q--)
  {
    cin>>x>>y; sum=0; rs=-INF;
    query(1,n,1); cout<<rs<<'\n';
  }

 return 0;
}