#include <iostream>
#include <fstream>
#define nmax 100005
#define inf (1LL<<60)
#define ll long long
using namespace std;

ll v[nmax], s[nmax], H[4*nmax], L[4*nmax], R[4*nmax];
ll n, m, currSum, bestSum, a, b;

ll sum(int lo, int hi) { return (s[hi] - s[lo-1]); }
ll max(ll a, ll b) { return a > b? a : b; }

void build(int node, int lo, int hi) {
	if(lo == hi) {
		L[node] = H[node] = R[node] = v[lo];
		return;
	}

	int mid = (lo + hi) >> 1;
	build(2*node, lo, mid);
	build(2*node+1, mid+1, hi);

	H[node] = max(max(H[2*node], H[2*node+1]), R[2*node]+L[2*node+1]);

	L[node] = max(L[2*node], sum(lo, mid) + L[2*node+1]);
	R[node] = max(R[2*node+1], R[2*node] + sum(mid+1, hi));
}

void query(int node, int lo, int hi, int a, int b) {
	if(a <= lo && hi <= b) {
		bestSum = max(max(bestSum, H[node]), max(currSum, currSum + L[node]));
		currSum = max(currSum + sum(lo, hi), R[node]);
		return;
	}

	int mid = (lo + hi) >> 1;

	if(a <= mid) query(2*node, lo, mid, a, b);
	if(mid < b)  query(2*node+1, mid+1, hi, a, b);
}

int main() {
	ifstream f("sequencequery.in");
	ofstream g("sequencequery.out");

	f>>n>>m;
	for(int i=1; i<=n; i++) { f>>v[i]; s[i] = s[i-1] + v[i]; }

	build(1, 1, n);

	for(int i=1; i<=m; i++) {
		f>>a>>b;
		bestSum = currSum = -inf;

		query(1, 1, n, a, b);
		g<<bestSum<<"\n";
	}

	return 0;
}