#include <iostream>
#include <fstream>

using namespace std;

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

typedef long long lint;
struct fren{
	lint lt, rt, t;
	lint ins, maxi;
	void imfrunza(lint x){
		maxi = ins = t = x;
		lt = rt = max(x, 0ll);
	}
};


int n, m;
fren tre[410000];

lint ele[100041];

fren mer(const fren & lhs, const fren & rhs){
	fren r;
	r.lt = max(lhs.lt, lhs.t+rhs.lt);
	r.rt = max(rhs.rt, rhs.t+lhs.rt);
	r.t = rhs.t+lhs.t;
	r.ins = max(lhs.rt+rhs.lt, max(lhs.ins, rhs.ins));
	r.maxi = max(lhs.maxi, rhs.maxi);
	return r;
}

fren bob(int lt = 1, int rt = n, int p = 1){
	fren & me = tre[p];
	if(lt == rt){
		me.imfrunza(ele[lt]);
	}else{
		int d = (lt+rt)/2;
		me = mer(bob(lt, d, 2*p), bob(d+1, rt, 2*p+1));
	}
	return me;
}

fren rec(int a, int b, int lt = 1, int rt = n, int p = 1){
	if(lt == a && rt == b){
		return tre[p];
	}
	int d = (lt+rt)/2;
	if(a >= lt && a <= d){
		if(b <= d){
			return rec(a, b, lt, d, 2*p);
		}else{
			return mer(rec(a, d, lt, d, 2*p), rec(d+1, b, d+1, rt, 2*p+1));
		}
	}else{
		return rec(a, b, d+1, rt, 2*p+1);
	}
}

lint usta(int a, int b){
	fren r = rec(a, b);
	if(r.maxi >= 0){
		return max(max(r.t, r.ins), max(r.lt, r.rt));
	}else{
		return r.maxi;
	}
}

bool fucme(int a, int b){
	int s = 0, maxi = ele[a];
	for(int i = a; i <= b; i++){
		s += ele[i];
		maxi = max(maxi, s);
		if(s < 0){
			s = 0;
		}
	}
	return (maxi==usta(a,b));
}

int main(){
	fin >> n >> m;
	
	for(int i = 1; i <= n; i++){
		fin >> ele[i];
	}
	bob();
	
	for(int i = 0; i < m; ++i){
		int a, b;fin >> a >> b;
		fout << usta(a, b) << "\n";
	}
	
	// for(int i = 1; i <= n; ++i){
	// 	for(int j = i; j <= n; ++j){
	// 		if(!fucme(i,j)){
	// 			cout << i << " " << j << "\n";
	// 		}
	// 	}
	// }
	return 0;
}