#include <stdio.h>
#define INF 1<<30
#define maxim(a,b) (((a)>(b))?(a):(b))
int poz,x,y;
long long s,MAX;
struct arb{int S,D,SD,sum;}A[200002];

void update(int nod,int l,int r){
  if (l==r){A[nod].S=A[nod].D=A[nod].SD=A[nod].sum=x;return;}
  int m=(l+r)>>1,fl=nod<<1,fr=fl|1;
  if (poz<=m)update(fl,l,m);
  else update (fr,m+1,r);
  A[nod].S = maxim( A[fl].S, A[fl].sum + A[fr].S );
  A[nod].D = maxim( A[fr].D, A[fl].D + A[fr].sum );
  A[nod].SD =maxim( maxim( A[fl].SD, A[fr].SD), A[fl].D + A[fr].S );
  A[nod].sum = A[fl].sum + A[fr].sum;
}

void query(int nod,int l,int r){
  if (x<=l&&r<=y){
    MAX = maxim( MAX, maxim( s + A[nod].S, A[nod].SD));
    s=maxim( s + A[nod].sum, A[nod].D);
    return;
  }
  int m=(l+r)>>1;
  if (x<=m)query(nod<<1,l,m);
  if (m< y)query((nod<<1)|1,m+1,r);
}

int main(){
  freopen("sequencequery.in","r",stdin); freopen("sequencequery.out","w",stdout);
  int n,m,i;
  scanf("%d %d",&n,&m);
  for (i=1;i<=n;++i){poz=i;scanf("%d",&x);update(1,1,n);}
  for (;m;--m){s=0;MAX=-INF;scanf("%d %d",&x,&y);query(1,1,n);printf("%lld\n",MAX);}
return 0;
}