#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
struct interval {
	int poz,st,dr;
};
long long s[400001],l[400001],r[400001],pozl[400001],pozr[400001],sum,su[100001];
int v[100001],n,bestsum,a,b,nr;
interval d[100001];
long long ssm(int p, int q)
{
	int i;
	long long max,s;
	s=0;
	max=-2000000000;
	for(i=p;i<=q;i++) {
		if(s<0)
			s=v[i];
		else s=s+v[i];
		if(s>max)
			max=s;
	}
	return max;
}
long long maxim(long long a, long long b)
{
	if(a>=b)
		return a;
	return b;
}
void update(int nod, int st, int dr)
{
	int mij,i,poz;
	long long smax,sum;
	if(st==dr) {
		s[nod]=v[st];
		l[nod]=v[st];
		r[nod]=v[st];
		pozr[nod]=st;
		pozl[nod]=st;
		return;
	}
	mij=(st+dr)/2;
	update(nod*2,st,mij);
	update(nod*2+1,mij+1,dr);
	smax=-2000000000;
	sum=0;
	poz=st;
	for(i=dr;i>=st;i--) {
		sum=sum+v[i];
		if(sum>smax) {
			smax=sum;
			poz=i;
		}
	}
	r[nod]=smax;
	pozr[nod]=poz;
	smax=-2000000000;
	sum=0;
	poz=dr;
	for(i=st;i<=dr;i++) {
		sum=sum+v[i];
		if(sum>smax) {
			smax=sum;
			poz=i;
		}
	}
	l[nod]=smax;
	pozl[nod]=poz;
	s[nod]=maxim((r[nod*2]+l[nod*2+1]),ssm(st,dr));
}
void query(int nod, int st, int dr)
{
	int mij;
	if((a<=st)&&(dr<=b)) {
		if(bestsum<maxim(s[nod],sum+l[nod])) 
			bestsum=maxim(s[nod],sum+l[nod]);
		if (sum+su[dr]-su[st-1]>r[nod])
			sum=sum+su[dr]-su[st-1];
		else sum=r[nod];
		return;
	}
	mij=(st+dr)/2;
	if (a<=mij)
		query(2*nod,st,mij);
	if (b>mij)
		query(2*nod+1,mij+1,dr);
}
int main ()
{
	int i,m;
	ifstream f("sequencequery.in");
	ofstream g("sequencequery.out");
	f>>n>>m;
	for(i=1;i<=n;i++) {
		f>>v[i];
		su[i]=su[i-1]+v[i];
	}
	update(1,1,n);
	for(i=1;i<=m;i++) {
		f>>a>>b;
		bestsum=-2000000000;
		nr=0;
		sum=0;
		query(1,1,n);
		g<<bestsum<<'\n';
	}
	f.close();
	g.close();
	return 0;
}