#include<stdio.h>
#define mare 1<<30

using namespace std;

int n,m,start,finish,v[300010]; 
long long sum[400070];
long long a[400000],b[400000],c[400000],s,bests;
long long max (long long a, long long b)
{
	if(a>b) return a;
	return b;
}

void update(int nod, int st, int dr)
{
	long m;
	m=(st+dr)/2;
	if(st==dr)
	{
		a[nod]=b[nod]=c[nod]=sum[nod]=v[st];
	}
	else
	{
		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[nod*2+1]);  
		sum[nod]=sum[nod*2]+sum[nod*2+1];  
	}
}
void query(int nod, int st, int 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;
}