#include<iostream>
#include<fstream>
using namespace std;
long long s[400001],l[400001],r[400001],sum,su[400001],bestsum;
int v[100001],n,a,b;
long long maxim(long long a, long long b)
{
	if(a>=b)
		return a;
	return b;
}
void update(int nod, int st, int dr)
{
	long long mij;
	if(st==dr) {
		s[nod]=v[st];
		l[nod]=v[st];
		r[nod]=v[st];
		su[nod]=v[st];
		return;
	}
	mij=(st+dr)/2;
	update(nod*2,st,mij);
	update(nod*2+1,mij+1,dr);
	s[nod]=maxim((r[nod*2]+l[nod*2+1]),maxim(s[nod*2],s[nod*2+1]));
	su[nod]=0LL+su[nod*2]+su[nod*2+1];
	r[nod]=0LL+su[nod*2+1]+r[nod*2];
	if(r[nod]<r[nod*2+1])
		r[nod]=r[nod*2+1];
	l[nod]=0LL+su[nod*2]+l[nod*2+1];
	if(l[nod]<l[nod*2])
		l[nod]=l[nod*2];
}
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[nod]>r[nod])
			sum=sum+su[nod];
		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];
	update(1,1,n);
	for(i=1;i<=m;i++) {
		f>>a>>b;
		bestsum=-2000000000;
		sum=0;
		query(1,1,n);
		g<<bestsum<<'\n';
	}
	f.close();
	g.close();
	return 0;
}