#include<iostream>
#include<fstream>
using namespace std;

ifstream in("sequencequery.in");
ofstream out("sequencequery.out");

const int N = 500010;

struct nod {
	long long min,max,smax;
};

long long n,m,a[N],px,py,smax,minp,maxs;
nod x[N];

void update(int nod, int pozx, int pozy) {
	if(pozx==pozy) {
		x[nod].max = a[pozx];
		x[nod].min = a[pozx-1];
		x[nod].smax = a[pozx] - a[pozx-1];
		return;
	}
	int mid = (pozx+pozy)/2;
	update(nod*2, pozx, mid);
	update(nod*2+1, mid+1,pozy);
	
	x[nod].max = max(x[nod*2].max, x[nod*2+1].max);
	x[nod].min = min(x[nod*2].min, x[nod*2+1].min);
	x[nod].smax = max(x[nod*2+1].max - x[nod*2].min, max(x[nod*2+1].smax, x[nod*2].smax));
}

void query(int nod, int pozx, int pozy) {
    if (px <= pozx && pozy <= py) {
        
		if(x[nod].smax>maxs)
			maxs=x[nod].smax;
		
		if(minp!=1<<25) {
			if(maxs < x[nod].max - minp)
				maxs = x[nod].max - minp;
			
			minp = min(minp, x[nod].min);
		}
		else
			minp=x[nod].min;
		return;
    }
	int mid = (pozx + pozy) / 2;
	if(px<=mid)
		query(2*nod,pozx,mid);
	if(mid+1<=py)
		query(2*nod+1,mid+1,pozy);
}

int main() {
	int i;
	
	in >> n >> m;
	
	for(i=1;i<=n;++i) {
		in >> a[i];
		a[i]+=a[i-1];
	}
	
	update(1,1,n);
	
	for(i=1;i<=m;++i) {
		in >> px >> py;
		
		minp=1<<25;
		maxs=-100000;
		query(1,1,n);
		
		out << maxs << "\n";
	}
	
	return 0;
}