#include<fstream>
#define DIM 100004
using namespace std;
int L[DIM],R[DIM],S[DIM],v[DIM];
int n,m,poz,a,b,s,rez;
void query(int nod,int st,int dr);
void update(int nod,int st,int dr);
int inline maxim(int a,int b);
ofstream fout("sequencequery.out");
int main()
{
	ifstream fin("sequencequery.in");
	fin>>n>>m;
	int i,j;
	for(i=1;i<=n;i++)
	{
		fin>>a;
		poz=i;
		update(1,1,n);  
	}
	for(i=1;i<=m;i++)
	{
		fin>>a>>b;
		rez=-32423423;
		s=0;
		query(1,1,n);
		fout<<rez<<"\n";
	}
	return 0;
}
void update(int nod,int st,int dr)
{
	if(st==dr)
	{
		v[nod]=L[nod]=R[nod]=S[nod]=a;
		return;
	}
	else
	{
		int mij=(st+dr)/2;
		if(poz<=mij)
		   update(2*nod,st,mij);
		else
		   update(2*nod+1,mij+1,dr);
	 }
	 L[nod]=maxim(L[2*nod],S[2*nod]+L[2*nod+1]);
	 R[nod]=maxim(R[2*nod+1],R[2*nod]+S[2*nod+1]);
	 v[nod]=maxim(maxim(v[2*nod],v[2*nod+1]),R[2*nod]+L[2*nod+1]);
	 S[nod]=S[2*nod]+S[2*nod+1];
}
void query(int nod,int st,int dr)
{
	if(st>=a && dr<=b)
	{
		rez=maxim(rez,maxim(s+L[nod],v[nod]));
		s=maxim(s+S[nod],R[nod]);
		return ;
	}
	else
	{
		int mij=(st+dr)/2;
		if(a<=mij)
		  query(2*nod,st,mij);
		if(b>mij)
		  query(2*nod+1,mij+1,dr);
	  }
}
int inline maxim(int a,int b)
{
	if(a>b)
	  return a;
	else
	  return b;
}