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

using namespace std;
int N;
int i, j, k, l;
int  v[200001];
int  B[800001];
int BS[800001];
int BD[800001];
int  S[800001];
int CC = 0, QQ = 0; //rezerva
int p1, p2;
void repara(int nod, int a, int 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] = S[2*nod] + S[2*nod+1];
	B[nod] = B[2*nod]; if (B[2*nod+1] > B[nod]) B[nod] = B[2*nod+1];
	if (BS[2*nod+1] + BD[2*nod] > B[nod]) B[nod] = BS[2*nod+1] + BD[2*nod];
	BS[nod] = BS[2*nod]; if (S[2*nod] + BS[2*nod+1] > BS[nod]) BS[nod] = S[2*nod] + BS[2*nod+1];
	BD[nod] = BD[2*nod+1]; if (S[2*nod+1] + BD[2*nod] > BD[nod] ) BD[nod] = S[2*nod+1]+BD[2*nod];
	if (BS[nod] > B[nod]) B[nod] =BS[nod];
	if (BD[nod] > B[nod]) B[nod] = BD[nod];
	}
int solve(int nod, int a, int b, int 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];}
		};
	int mid = a + b; mid/=2;
	int 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);
	int M;
	scanf("%d", &N);
	scanf("%d", &M);
	for (i=1; i<=N; i++) { scanf("%d", &v[i]); CC = v[i]; QQ = i; repara(1, 1, N);}

	
	while (M--) {
		int a1, a2, a3;
		scanf("%d %d", &a2, &a3);
		p1 = a2; p2 = a3;
		QQ = solve(1, 1, N,  3);
		printf("%d\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; printf("%d\n", QQ);
			}*/
		}
	return 0;
}