#include <fstream>
#include <iostream>
#include <algorithm>

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

struct ARBORE{
	long long rbest,lbest,best,sum;
	ARBORE(){
		rbest = lbest = sum = best = -1000000;
	}
};

ARBORE ARB[400010];
int el,ind,N,st,dr,M;

int maxi(long long a,long long b,long long c){
	if(a < 0 && b < 0) return (a < b) ? b : a;
	if(a < b) a = b;
	return (a > c) ? a : c;
}
void addel(int l,int r,int pos){
	if(l >= r){
		ARB[pos].lbest = ARB[pos].rbest = ARB[pos].sum = ARB[pos].best = el;
		return;
	}
	
	int mid = (l+r)/2;
	if(ind <= mid) addel(l,mid,pos*2);
	else addel(mid+1,r,pos*2+1);
	
}

void gen(int l,int r,int pos){
	if(l >= r) return;

	gen(l,(l+r)/2,pos*2);
	gen((l+r)/2+1,r,pos*2+1);
	ARB[pos].best = maxi(ARB[pos*2].best,ARB[pos*2+1].best,ARB[pos*2].rbest+ARB[pos*2+1].lbest);
	ARB[pos].sum = ARB[pos*2].sum + ARB[pos*2+1].sum;
	ARB[pos].lbest = max(ARB[pos*2].lbest,ARB[pos*2].sum+ARB[pos*2+1].lbest); 
	ARB[pos].rbest = max(ARB[pos*2+1].rbest,ARB[pos*2+1].sum+ARB[pos*2].rbest);
	
}

ARBORE querry(int l,int r,int pos){
	if(l >= st && r <= dr) return ARB[pos];
	ARBORE rs,a,b;
	int mid = (l+r)/2;
	if( st <= mid ) a = querry(l,mid,pos*2);
	if(dr > mid) b = querry(mid+1,r,pos*2+1);
	rs.best = maxi(a.best,b.best,a.rbest+b.lbest);
	rs.sum = a.sum + b.sum;
	rs.lbest = max(a.lbest,a.sum+b.lbest);
	rs.rbest = max(b.rbest,a.rbest + b.sum);
	return rs;
}


int main(){
	fin >> N >> M;
	for(ind = 1;ind<=N;ind++){
		fin >> el;
		addel(1,N,1);
	}

	gen(1,N,1);
	
	for(int i = 0;i<M;i++){
		fin >> st >> dr;
		fout << querry(1,N,1).best << '\n';
	}
	
	
	return 0;
}