#include <cstdio>
#include <algorithm>

#define getCommon int m = (l + r) >> 1, fs = m << 1, fd = fs | 1
#define MAXN 100010
#define ll long long
using namespace std;

struct omg {
	int st, dr, sum, smx;
} B[MAXN * 4];

int N, M, A[MAXN], px, py;
ll s, ax;
inline ll max(ll a, ll b) {
	if(a > b) return a;
	return b;
}
void build_tree(int nod, int l, int r) {
	if(l == r) {
		B[nod].st = B[nod].dr = A[l];
		B[nod].sum  =  B[nod].smx = A[l];
		return ;
	}
	getCommon;
	build_tree(fs, l, m);
	build_tree(fd, m + 1, r);

	B[nod].sum = B[fs].sum + B[fd].sum;
	B[nod].st = max(B[fs].st, B[fs].sum + B[fd].st);
	B[nod].dr = max(B[fd].dr, B[fd].sum + B[fs].dr);
	B[nod].smx= max(B[nod].sum, max(B[fs].dr + B[fd].st, max(B[fs].smx, B[fd].smx)));
}
void query_tree(int nod, int l, int r) {
	if(px <= l && py >= r) {
		if(ax < 0) ax = 0;
		s = max(s, max(B[nod].smx, ax + B[nod].st));
		ax = max(ax + B[nod].sum, B[nod].dr);
		return ;
	}
	getCommon;
	if(px <= m) query_tree(fs, l, m);
	if(m < py) query_tree(fd, m + 1, r);
}
int main() {

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

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

	for(int i = 1; i <= N; i++)
		scanf("%d", &A[i]);

	build_tree(1, 1, N);
	for(int i = 1; i <= M; i++) {
		scanf("%d %d\n", &px, &py);
		s = -1000000000; ax = 0;
		query_tree(1, 1, N);
		printf("%lld\n", s);
	}
	return 0;
}