#pragma GCC optimize("03")
#include <bits/stdc++.h>
#define N 100010
#define L (pos << 1)
#define R (L | 1)
#define INF -10000000000000

using namespace std;

ifstream in("sequencequery.in");
ofstream out("sequencequery.out");

struct lol{
	long long bst, sum, l, r;
};

int n, m, a[N], x, y;
lol h[4 * N];

lol mix(const lol &a, const lol &b){
	lol nod;
	nod.bst = max({a.bst, b.bst, a.r + b.l});
	nod.sum = a.sum + b.sum;
	nod.l = max(a.l, a.sum + b.l);
	nod.r = max(b.r, b.sum + a.r);
	return nod;
}

void build(int st, int dr, int pos){
	if(st == dr){
		h[pos].bst = h[pos].sum = h[pos].l = h[pos].r = a[st];
		return;
	}
	int mid = st + dr >> 1;
	build(st, mid, L);
	build(mid + 1, dr, R);
	h[pos] = mix(h[L], h[R]);
}

lol query(int st, int dr, int pos, int l, int r){
	if(l <= st && dr <= r)
		return h[pos];
	int mid = st + dr >> 1;
	lol left, right;
	left = right = {INF, INF, INF, INF};
	if(l <= mid)
		left = query(st, mid, L, l, r);
	if(r > mid)
		right = query(mid + 1, dr, R, l, r);
	return mix(left, right);
}

int main(){
	in >> n >> m;
	for(int i = 1; i <= n; i++)
		in >> a[i];
	build(1, n, 1);
	while(in >> x >> y)
		out << query(1, n, 1, x, y).bst << '\n';
	return 0;
}