#include <iostream>
#include <fstream>
using namespace std;
#define MAX 100100
#define INF 0x3f3f3f3f

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

int N, Q;
int V[MAX], SumSt[MAX], SumDr[MAX], SumStMax[MAX], SumDrMax[MAX], ISt[MAX], IDr[MAX];
int Tree[MAX*4], Lx, Ly;

void LoadData() {
	In >> N >> Q;
	for (int i=1; i<=N; ++i)
		In >> V[i];
}

int Brut(int LSt, int LDr) { 
	int i, S=0, R=-INF;
	for (i=LSt; i<=LDr; ++i) {
		S += V[i];
		R = max(R, S);
		if ( S<0 ) S = 0;
	}
	return R;
}

void Prepare() {
	int px, i;
	for (i=1; i<=N; ++i) {
		SumSt[i] = SumSt[i-1] + V[i];
		SumDr[N-i+1] = SumDr[N-i+2] + V[N-i+1];
	}
	for (px=i=1; i<=N; ++i) {
		SumStMax[i] = SumSt[i] - SumSt[px-1];
		ISt[i] = px;
		if ( SumSt[i] < SumSt[px-1] ) px = i+1;
	}
	for (px=i=N; i; --i) {
		SumDrMax[i] = SumDr[i] - SumDr[px+1];
		IDr[i] = px;
		if ( SumDr[i] < SumDr[px+1] ) px = i-1;
	}
}

void BuildTree(int Node, int LSt, int LDr) {
	if ( LSt == LDr ) {
		Tree[Node] = V[LSt];
		return ;
	}
	int M = (LSt+LDr) / 2;
	BuildTree(Node*2+1, LSt, M);
	BuildTree(Node*2+2, M+1, LDr);

	int St = SumStMax[M]-(SumSt[LSt-1]-SumSt[ISt[M]-1])*(ISt[M]<LSt);
	int Dr = SumDrMax[M+1]-(SumDr[LDr+1]-SumDr[IDr[M+1]+1])*(IDr[M+1]>LDr);
	Tree[Node] = max(max(Tree[Node*2+1], Tree[Node*2+2]), St+Dr);
	return;
	if ( Tree[Node] != Brut(LSt, LDr) )
		Out << "** EROARE la " << Node << " " << LSt << " " << LDr << " " << Tree[Node] << "!=" << Brut(LSt, LDr) << "\n";
}

int QueryTree(int Node, int LSt, int LDr) {
	if ( Lx<=LSt && LDr<=Ly ) 
		return Tree[Node];
	int R = -INF;
	int M = (LSt+LDr) / 2;
	if ( Lx <= M ) 
		R = max(R, QueryTree(Node*2+1, LSt, M));
	if ( M < Ly ) 
		R = max(R, QueryTree(Node*2+2, M+1, LDr));
	if ( Lx <= M && M < Ly ) {
		int St = SumStMax[M]-(SumSt[Lx-1]-SumSt[ISt[M]-1])*(ISt[M]<Lx);
		int Dr = SumDrMax[M+1]-(SumDr[Ly+1]-SumDr[IDr[M+1]+1])*(IDr[M+1]>Ly);
		R = max(R, St+Dr);
	}
	return R;
}

void Solve() {
	while ( Q-- ) {
		In >> Lx >> Ly;
//		Out << Brut(Lx, Ly) << "\n";
		Out << QueryTree(0,1,N) << "\n";
	}
}

int main() {
	LoadData();
	Prepare();
	BuildTree(0, 1, N);
	Solve();
	return 0;
}