#include <fstream>

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

struct nod{
	long long negl,best,negr,sum;
	nod(){
		negl = 1;
		negr = best = sum = 0;
	}
};

nod ARB[262147];
int ind,N,M,st,dr;

int maxi(long long  a, long long b,long long c){
	if(a < b) a = b;
	if(a < c) a = c;
	return a; 
}

void add(int l,int r,int pos,int k){
	if(l == r){
		ARB[pos].best = ARB[pos].sum = k;
		if(k < 0){
			ARB[pos].negl = k;
			ARB[pos].negr = k;
		}else{
			ARB[pos].negl = 0;
			ARB[pos].negr = 0;
		}
		return;
	}
	
	int mid = (l+r)/2;
	if(ind > mid) 
		add(mid+1,r,pos*2+1,k); 
	else
		add(l,mid,pos*2,k);
}

nod init(int l,int r,int pos){
	nod a,b;
	if(l != r){
		a = init(l,(l+r)/2,pos*2);
		b = init((l+r)/2+1,r,pos*2+1);
		ARB[pos].sum = a.sum + b.sum;
		ARB[pos].best = maxi(a.best,a.best+b.best+a.negr+b.negl,b.best); 
		if(ARB[pos].best == a.best+b.best+a.negr+b.negl){
			ARB[pos].negl = a.negl; 
			ARB[pos].negr = b.negr;
		}else
		if(ARB[pos].best == a.best){
			ARB[pos].negr = a.negr + b.sum;
			ARB[pos].negl = a.negl;
		}else{
			ARB[pos].negl = b.negl + a.sum;
			ARB[pos].negr = b.negr;			
		}
	}
	return ARB[pos];
}



nod querry(int l,int r, int pos){
	if((l == st && dr == r) || (l == r)){
		return ARB[pos];
	}
	
	int mid = (l+r)/2;
	nod rs,a,b;
	if(st <= mid) a = querry(l,mid,pos*2);
	if(dr > mid)  b = querry(mid+1,r,pos*2+1);
	if(a.negl <= 0 && b.negl <= 0){
		rs.sum = a.sum + b.sum;
		rs.best = maxi(a.best,a.best+b.best+a.negr+b.negl,b.best);
		if(rs.best == a.best+b.best+a.negr+b.negl){
			rs.negl = a.negl; 
			rs.negr = b.negr;
		}else
		if(rs.best == a.best){
			rs.negr = a.negr + b.sum;
			rs.negl = a.negl;
		}else{
			rs.negl = b.negl + a.sum;
			rs.negr = b.negr;			
		}
	}
	else if (a.negl <= 0) rs = a;
	else rs = b;
	
	return rs;
}


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