// #include <iostream>
#include <fstream>

using namespace std;
int n,m,x,y;
int ma,s;

ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
const int MAXN = 4e5 + 5;
int aints[MAXN];
int aintSM[MAXN];
int aintL[MAXN] ;
int aintR[MAXN];


void update(int nod, int l , int r, int poz, int val) {
	if(l == r) {
	aintL[nod] = aintR[nod] = aints[nod] = aintSM[nod] = val;
	return;
}
int mj = (l + r) >> 1;
if(mj >= poz)
	update(nod*2,l,mj,poz,val);
else
	update(nod*2+1,mj+1,r,poz,val);
aints[nod] =  aints[nod*2] + aints[nod*2+1];
aintSM[nod] = max(aintSM[nod*2],max(aintSM[nod*2+1],aintR[nod*2] + aintL[nod*2+1]));
aintL[nod]= max(aintL[nod*2],aints[nod*2] + aintL[nod*2+1]);
aintR[nod]= max(aintR[nod*2+1],aintR[nod*2+1] + aintR[nod*2]);

}

void query(int nod, int l, int r, int x, int y){
	if(l >= x and r <= y){
		ma = max(ma,aintSM[nod]);
		ma = max(ma,s + aintL[nod]);
		s = max(s+aints[nod],aintR[nod]);
	return;
}
	int mj = (l + r) >> 1;
	if(x <= mj)
	query(nod*2,l,mj,x,y);
	if(y > mj)
	query(nod*2+1,mj+1,r,x,y);
}

int main() {

	cin >> n >> m;
	for ( int i = 1; i <= n; ++i) {
		cin >>x;
		update(1,1,n,i,x);
}
	for ( int i = 1; i <= m; ++i) {
        cin >> x >> y;
		ma = - (1<<30);
		s = 0;
		query(1,1,n,x,y);
		cout << ma <<"\n";
}
}