#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;
const int NMAX = 4e5+5;

int v[NMAX];
ll aib_l[NMAX], aib_r[NMAX];
ll aib_pref[NMAX], sum[NMAX];

void update(int node, int l, int r, int pos, int val){
	if(l == r){
		aib_l[node] = val;
		aib_r[node] = val;
		aib_pref[node] = val;
		sum[node] = val;
		return;
	}

	int mid = (l+r)/2;
	if(pos <= mid)
		update(node*2, l, mid, pos, val);
	else
		update(node*2+1, mid+1, r, pos, val);

	sum[node] = sum[node*2] + sum[node*2+1];

	aib_l[node] = max(aib_l[node*2], aib_l[node*2+1] + sum[node*2]);
	aib_r[node] = max(aib_r[node*2+1], aib_r[node*2] + sum[node*2+1]);

	aib_pref[node] = max(aib_pref[node*2], aib_pref[node*2+1]);
	aib_pref[node] = max(aib_pref[node], aib_r[node*2] + aib_l[node*2+1]);
}

ll sol, aux;
ll query(int node, int l, int r, int a, int b){
	if(a <= l && r <= b){
		sol = max(sol, aib_pref[node]);
		sol = max(sol, aux + aib_l[node]);
		aux = max(aux + sum[node], aib_r[node]);
		return sum[node];
	}

	int mid = (l+r)/2;

	ll ret = 0;
	if( a<= mid)
		ret += query(node*2, l, mid, a, b);
	if(b > mid)
		ret += query(node*2+1, mid+1, r, a, b);

	return ret;
}

void solve(){

	int n, m;
	scanf("%d %d", &n, &m);

	for(int i=1; i<=n; ++i){
		scanf("%d", &v[i]);
		update(1, 1, n, i, v[i]);
	}

	int x, y;
	for(int i=0; i<m; ++i){
		scanf("%d %d", &x, &y);
		sol = -1e9, aux = -1e9;
		printf("%lld\n", max(query(1, 1, n, x, y), max(sol, aux)));
	}

}

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

	int t = 1;

	for(int i=0; i<t; ++i){
		solve();
	}

	return 0;
}