#include <cstdio>
#include <cstring>

const int maxn = 100010;
const int maxnode = maxn * 3;

#define left(v) ((v) << 1)
#define right(v) (((v) << 1) + 1)
#define min(a, b) ((a) < (b) ? (a) : (b))
#define max(a, b) ((a) > (b) ? (a) : (b))

typedef long long LL;

struct tNode {
	LL sum, best; // sum = sum of whole range, best = best answer of that range
	LL lsum, rsum; // lsum = best sum of substring start at l, rsum = best sum of substring ends at r
};

tNode tree[maxnode];
int n, m, a[maxn], nlist;
tNode list[maxnode];
int suffix[maxnode], prefix[maxnode];

void updateNode(int node) {
	int lnode = left(node), rnode = right(node);
	tree[node].sum = tree[lnode].sum + tree[rnode].sum;
	tree[node].lsum = max(tree[lnode].lsum, tree[lnode].sum + tree[rnode].lsum);
	tree[node].rsum = max(tree[rnode].rsum, tree[lnode].rsum + tree[rnode].sum);
	tree[node].best = tree[lnode].rsum + tree[rnode].lsum;
	tree[node].best = max(tree[node].best, max(tree[lnode].best, tree[rnode].best));		
	tree[node].best = max(tree[node].best, max(tree[node].sum, max(tree[node].lsum, tree[node].rsum)));
}

void update(int node, int l, int r, int x, int v) {
	if (l == r && r == x) {
		tree[node].sum = tree[node].lsum = tree[node].rsum = tree[node].best = v;
		return;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) update(left(node), l, mid, x, v);
	else
		update(right(node), mid + 1, r, x, v);
	updateNode(node);
//	printf("%d %d best = %I64d sum = %I64d lsum = %I64d rsum = %I64d\n", l, r, tree[node].best, tree[node].sum, tree[node].lsum, tree[node].rsum);
}

void getNode(int node, int l, int r, int a, int b) {
	if (a <= l && r <= b) {
		list[++nlist] = tree[node];
//		printf("l = %d r = %d\n", l, r);
		return;
	}
	int mid = (l + r) >> 1;
	if (a <= mid) getNode(left(node), l, mid, a, b);
	if (mid < b) getNode(right(node), mid + 1, r, a, b);
}

LL getMax() {
	LL ret = -2000000000;
	suffix[1] = list[1].rsum;
	for (int i = 2; i < nlist; ++i) suffix[i] = max(suffix[i - 1] + list[i].sum, list[i].rsum);
	prefix[nlist - 1] = list[nlist].lsum;
	for (int i = nlist - 2; i >= 1; --i) prefix[i] = max(prefix[i + 1] + list[i + 1].sum, list[i + 1].lsum);
	for (int i = 1; i < nlist; ++i) ret = max(ret, prefix[i] + suffix[i]);
	for (int i = 1; i <= nlist; ++i) ret = max(ret, list[i].best);
	return ret;
}

int main() {
	freopen("sequencequery.in", "r", stdin);
	freopen("sequencequery.out", "w", stdout);
	scanf("%d %d", &n, &m);
	memset(tree, 0, sizeof(tree));
	for (int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
		update(1, 1, maxn, i, a[i]);
	}
	
	int l, r;
	for (int i = m; i--; ) {
		scanf("%d %d", &l, &r);
		nlist = 0;
		getNode(1, 1, maxn, l, r);
		printf("%lld\n", getMax());
	}
	return 0;
}