#include <iostream>
#include <fstream>
using namespace std;
#define MAX 100100
const long long INF = ((long long)MAX)*MAX;

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

int N, Q;
int A[MAX];
long long V[MAX], Min[4*MAX], Max[4*MAX], Best[4*MAX];
int Lx, Ly;

inline long long max(long long A, long long B) { return A>B ? A : B; }
inline long long min(long long A, long long B) { return A<B ? A : B; }

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

long long Brut(int LSt, int LDr) { 
	int i;
	long long 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";
}

long long QueryMaxTree(int N, int L, int R, int XL, int XR) {
	if ( XL<=L && R<=XR )
		return Max[N];
	int M = (L+R) / 2;
	long long 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;
}

long long QueryMinTree(int N, int L, int R, int XL, int XR) {
	if ( XL<=L && R<=XR )
		return Min[N];
	int M = (L+R) / 2;
	long long 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;
}

long long QueryBestTree(int N, int L, int R) {
	if ( Lx <= L && R <= Ly ) 
		return Best[N];
	int M = (L+R) / 2;
	long long 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;
}