#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 A[MAX], V[MAX], Min[4*MAX], Max[4*MAX], Best[4*MAX];
int Lx, Ly;

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

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

void BuildTree(int N, int L, int R) {
	if ( L==R ) {
		Best[N] = A[L];
		Max[N] = V[L];
		Min[N] = V[L-1];
		return ;
	}
	int M = (L+R) / 2;
	BuildTree(2*N+1, L, M);
	BuildTree(2*N+2, M+1, R);
	Min[N] = min(Min[2*N+1], Min[2*N+2]);
	Max[N] = max(Max[2*N+1], Max[2*N+2]);
	Best[N] = max(max(Best[2*N+1], Best[2*N+2]), Max[2*N+2]-Min[2*N+1]);
//	Out << "*" << N << " " << L << " " << R << " : " << Best[N] << " // " << Brut(L, R) << "\n";
}

int QueryMaxTree(int N, int L, int R, int XL, int XR) {
	if ( XL<=L && R<=XR )
		return Max[N];
	int M = (L+R) / 2;
	int Ret = -INF;
	if ( XL <= M )
		Ret = max(Ret, QueryMaxTree(2*N+1, L, M, XL, XR));
	if ( M < XR ) 
		Ret = max(Ret, QueryMaxTree(2*N+2, M+1, R, XL, XR));
	return Ret;
}

int QueryMinTree(int N, int L, int R, int XL, int XR) {
	if ( XL<=L && R<=XR )
		return Min[N];
	int M = (L+R) / 2;
	int Ret = INF;
	if ( XL <= M )
		Ret = min(Ret, QueryMinTree(2*N+1, L, M, XL, XR));
	if ( M < XR ) 
		Ret = min(Ret, QueryMinTree(2*N+2, M+1, R, XL, XR));
	return Ret;
}

int QueryBestTree(int N, int L, int R) {
	if ( Lx <= L && R <= Ly ) 
		return Best[N];
	int M = (L+R) / 2;
	int Ret = -INF;
	if ( Lx <= M )
		Ret = max(Ret, QueryBestTree(2*N+1, L, M));
	if ( M < Ly ) 
		Ret = max(Ret, QueryBestTree(2*N+2, M+1, R));
	if ( Lx <= M && M < Ly )
		Ret = max(Ret, QueryMaxTree(2*N+2, M+1, R, Lx, Ly)-QueryMinTree(2*N+1, L, M, Lx, Ly));
	return Ret;
}

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

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