#include <fstream>
 
using namespace std;
 
ifstream fin ("sequencequery.in");
ofstream fout ("sequencequery.out");
 
const int Dim = 100001;
long long AintL[Dim * 4],AintR[Dim * 4],n,A[Dim],m,AintM[Dim * 4],AintS[Dim * 4],s,ma;
 
void Query(long long nod, long long le , long long ri, long long x, long long y);
void Update(long long nod, long long le, long long ri , long long poz, long long val);
 
int main() {
	
	fin >> n >> m;
	for ( long long i = 1; i <= n; ++i)
		fin >> A[i], Update(1,1,n,i,A[i]);
	long long x,y;
	for ( ; m > 0; --m) {
		fin >> x >> y;
		ma = - 1LL << 50;
		s = 0;
		Query(1,1,n,x,y);
		fout << ma << "\n";
	}
}
 
 
void Update(long long nod, long long le, long long ri , long long poz, long long val) {
	
	if ( le == ri) {
		AintL[nod] = AintR[nod] = AintM[nod] = AintS[nod] = val;
		return;
	}
	
	long long mj = ( le + ri ) / 2;
	if ( mj >= poz)
		Update(nod * 2, le , mj, poz, val);
	else
		Update(nod * 2 + 1, mj + 1 , ri, poz, val);
	AintS[nod] = AintS[nod * 2] + AintS[nod * 2 + 1];
	AintM[nod] = max(AintR[nod * 2] + AintL[nod * 2 + 1], max(AintM[nod * 2], AintM[nod * 2 + 1]));
	AintL[nod] = max(AintL[nod * 2], AintS[nod * 2] + AintL[nod * 2 + 1]);
	AintR[nod] = max(AintR[nod * 2 + 1], AintS[nod * 2 + 1] + AintR[nod * 2]);
}
 
void Query(long long nod, long long le , long long ri, long long x, long long y) {
	
	if (  x <= le and ri <= y) {
 
		ma = max(ma, AintM[nod]);
		ma = max(ma, s + AintL[nod]);
		s = max(s + AintS[nod], AintR[nod]);
		
		return;
	} 
	
	long long mj = ( le + ri ) / 2;
	if ( x <= mj)
		Query(nod * 2, le, mj , x, y);
	if ( y >= mj + 1)
		Query( nod * 2 + 1, mj + 1, ri, x, y);
}