#include <iostream>
#include <stdio.h>
#include <vector>
#include <limits>

using namespace std;

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

	int n, m;
	cin >> n >> m;

	vector<int> v(n);
	vector<int> sum(n+1);
	sum[0] = 0;

	for (int i = 0; i < n; i++) {
		cin >> v[i];
		sum[i+1] = sum[i] + v[i];
	}

	int x, y;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;

		int bestSum = v[x-1];
		int minim = sum[x-1];

		for (int i = x; i < y; i++) {
			int s = sum[i+1] - sum[x] - minim;
			if (s < minim)
				minim = s;
			if (bestSum < s)
				bestSum = s;
		}

		cout << bestSum << endl;
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}