#include<cstdio>
#include<algorithm>
#define Nmax 100010
#define INF (1<<30)
#define LEFT (nod<<1)
#define RIGHT (1+(nod<<1))
using namespace std;

struct Nod {
	long long left, right, best, sum;
} ArbInt[Nmax<<2], Best;

int N, M, X, A, B;

Nod merge_values(Nod st, Nod dr) {

	Nod merged;

	merged.left = max(st.left,  st.sum + dr.left);
	merged.right = max(dr.right, st.right + dr.sum);
	merged.best = max(st.best, dr.best);
	merged.best = max(merged.best, st.right + dr.left);
	merged.sum = st.sum + dr.sum;

	return merged;
}

void update(int nod, int s, int d, int pos, int val) {

	if (s == d) {
        ArbInt[nod].left = val;
        ArbInt[nod].right = val;
        ArbInt[nod].best = val;
        ArbInt[nod].sum = val;
        return;
	}

	int m = (s + d) >> 1;
	
	if (pos <= m) update(LEFT, s, m, pos, val);
	else		  update(RIGHT, m + 1, d, pos, val);

    ArbInt[nod] = merge_values(ArbInt[LEFT], ArbInt[RIGHT]);
}

void query(int nod, int s, int d, int a, int b) {

    if (a <= s && d <= b) {
        Best = merge_values(Best, ArbInt[nod]);
		return ;
	}

	int m = (s + d) >> 1;

	if (a <= m) query(LEFT, s, m, a, b);
	if (m < b)  query(RIGHT, m + 1, d, a, b);
}


int main() {

	freopen("sequencequery.in", "r", stdin);
	freopen("sequencequery.out", "w", stdout);

	scanf("%d %d", &N, &M);

	for (int i = 1 ; i <= N ; i++) {
        scanf("%d", &X);
		update(1, 1, N, i, X);

	}

	for (int i = 1 ; i <= M ; i++) {
		
		Best.left = -INF;
		Best.right = -INF;
		Best.best = -INF;
		Best.sum = 0;
		 
		
		scanf("%d %d", &A, &B);
		query(1, 1, N, A, B);
		printf("%lld\n", Best.best);
	}

	return 0;
}