/*sursa de la oni bynet*/
#include <cstdio>

using namespace std;
long N;
long i, j, k, l;
long  v[200001];
long  B[800001];
long BS[800001];
long BD[800001];
long  S[800001];
long CC = 0, QQ = 0; //rezerva
long p1, p2;
void repara(long nod, long a, long b) {
	if (b < a) return;
	if (QQ > b || QQ < a)  return;
	if (a==b) {B[nod] = CC; BS[nod] = CC; BD[nod] = CC; S[nod] = CC; return;};
	repara(2*nod, a, (a+b)/2);
	repara(2*nod+1, (a+b)/2+1, b);
	S[nod] = 0;
	if (a <= (a+b)/2) S[nod] = S[2*nod];
	if ((a+b)/2+1 <= b) S[nod]+=S[2*nod+1];
	B[nod] = S[nod];
	if (a <= (a+b)/2) if (B[2*nod] > B[nod]) B[nod] = B[2*nod];
	if ((a+b)/2+1 <= b && B[2*nod+1] > B[nod]) B[nod] = B[2*nod+1];
	if (a <= (a+b)/2 && (a+b)/2+1 <=b)
	if (BS[2*nod+1] + BD[2*nod] > B[nod]) B[nod] = BS[2*nod+1] + BD[2*nod];
	BS[nod] = S[nod];
	if (a <= (a+b)/2 && BS[2*nod] > BS[nod]) BS[nod] = BS[2*nod];
	if (a <= (a+b)/2 && (a+b)/2+1 <=b){
		if (S[2*nod] + BS[2*nod+1] > BS[nod]) BS[nod] = S[2*nod] + BS[2*nod+1];
		if (BD[2*nod] + BS[2*nod+1] > BS[nod]) BS[nod] = BD[2*nod]+BS[2*nod+1];
		}
	BD[nod] = S[nod];
	if (a<=(a+b)/2 && BD[2*nod+1] > BD[nod])
	BD[nod] = BD[2*nod+1]; 
	if (a <= (a+b)/2 && (a+b)/2+1 <=b){
		if (S[2*nod+1] + BD[2*nod] > BD[nod] ) BD[nod] = S[2*nod+1]+BD[2*nod];
		if (BS[2*nod+1] + BD[2*nod] > BD[nod] ) BD[nod] = BS[2*nod+1] + BD[2*nod];
	}

	if (BS[nod] > B[nod]) B[nod] =BS[nod];
	if (BD[nod] > B[nod]) B[nod] = BD[nod];
	}
long solve(long nod, long a, long b, long T) {
	if (p2 < a) return 0;
	if (p1 > b) return 0;
	if (p1 <= a && p2 >= b) {
		if (T == 0) { return S[nod]; }
		if (T == 1) {
			//if (BS[nod] < 0) return 0; 
			return BS[nod];}
		if (T == 2) {
			//if(BD[nod] < 0) return 0; 
			return BD[nod];}
		if (T == 3) {
			//if (B[nod] < 0) return 0;  
			return B[nod];}
		};
	long mid = a + b; mid/=2;
	long ret = 0;
	if (T == 0) return solve(2*nod, a, mid, 0) + solve(2*nod+1, mid+1, b, 0);
	if (T == 1) {
		//[p1....p2]
		//ret = 0;
		if (p1 <= mid &&p2 > mid) return solve(2*nod, a, mid, 0) + solve(2*nod+1, mid+1, b, 1);
		else if (p2 <= mid) return solve(2*nod, a, mid,  1);
		else return solve(2*nod+1, mid+1, b, 1);
		//[p1, mid] + t=1 -> [mid+1, p2];
		//[
		}
	if (T == 2) {
		if (p1 <= mid && p2 > mid) return solve(2*nod, a, mid,  2) + solve(2*nod+1, mid+1, b,  0);
		else if (p2 <= mid) return solve(2*nod, a, mid,  2);
		else return solve(2*nod+1, mid+1, b, 2);
		}
	if (T == 3) {
		if (p2 <= mid) return solve(2*nod, a, mid,  3);
		else if (p1 > mid) return solve(2*nod+1, mid+1, b,  3);
		else {
			return solve(2*nod, a, mid,  2) + solve(2*nod+1, mid+1, b, 1);
			}
		}
	}
int main() {
	freopen("sequencequery.in", "r", stdin);
	freopen("sequencequery.out", "w", stdout);
	long M;
	scanf("%ld", &N);
	scanf("%ld", &M);
	for (i=1; i<=N; i++) { scanf("%ld", &v[i]); CC = v[i]; QQ = i; repara(1, 1, N);}

	
	while (M--) {
		long a1, a2, a3;
		scanf("%ld %ld", &a2, &a3);
		p1 = a2; p2 = a3;
		QQ = solve(1, 1, N,  3);
		printf("%ld\n", QQ);
		/*
		if (a1 == 0) {CC = a3; QQ = a2+1; repara(1, 1, N);}
		else {
			QQ = -200000;	
			a2++; a3++;
			p1 = a2; p2 = a3;
			QQ = solve(1, 1, N,  3);
			if (QQ < 0) QQ = 0; prlongf("%d\n", QQ);
			}*/
		}
	return 0;
}