#include<stdio.h>
#define mare 1<<30
long long n,m,start,finish,val,pos,s,bests;  
long long sum[400070],v[100010];
long long a[400000],b[400000],c[400000];
long max (long a, long b)
{
	if(a>b) return a;
	return b;
}

void update(long nod, long st, long dr)
{
	long m;
	if(st==dr)
	{
		a[nod]=b[nod]=c[nod]=sum[nod]=v[st];
	}
	m=(st+dr)/2;
	update(2*nod, st, m);
	update(2*nod+1, m+1, dr);
	a[nod]=max(a[nod*2],sum[nod*2]+a[nod*2+1]);  
    b[nod]=max(b[nod*2]+sum[nod*2+1],b[nod*2+1]);  
    c[nod]=max(max(c[nod*2],c[nod*2+1]),b[nod*2]+a[n*2+1]);  
    sum[nod]=sum[nod*2]+sum[nod*2+1];  
}
void query(long nod, long st, long dr)
{
	long m;
	m=(st+dr)/2;
	if(start<=st && dr<=finish)  
    {   
		bests=max(bests,max(s+a[nod],c[nod]));  
        s=max(s+sum[nod],b[nod]);  
    }  
    else  
    {   if(start<=m)  query(2*nod, st, m);  
        if(finish>m)   query(2*nod+1, m+1, dr);  
    }  
}
int main()
{
	long i;
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	for(i=1;i<=n;++i)
		scanf("%ldz",&v[i]);
	update(1,1,n);
	for(i=1;i<=m;++i)
	{
		scanf("%ld%ld",&start,&finish);
		bests=s=-mare;
		query(1,1,n);
		printf("%ld\n",bests);
	}
	return 0;
}