#include <algorithm>
#include <iostream>
#include <fstream>
using namespace std;

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

const int Max = 100100;
const int LMax = 17;
const long long oo = 1000000000000000000LL;
int N, M;
int A[Max];
		
struct RMQ {
	long long left, middle, right, total;
};
RMQ rmq[LMax][Max];



void read() {
	fin >> N >> M;
	for (int i = 1; i <= N; i++)
		fin >> A[i];
}

void solve() {
	for (int j = 1; j <= N; j++)
		rmq[0][j].left = rmq[0][j].middle = rmq[0][j].right = rmq[0][j].total = A[j];
	for (int i = 1; i < LMax; i++)
		for (int j = 1; j <= N; j++) {
			int S1 = j, S2 = j + (1 << (i - 1));
			if (S2 + (1 << (i - 1)) - 1 > N) break;
			
			rmq[i][j].left = max(rmq[i - 1][S1].left, rmq[i - 1][S1].total + rmq[i - 1][S2].left);
			rmq[i][j].right = max(rmq[i - 1][S2].right, rmq[i - 1][S2].total + rmq[i - 1][S1].right);
			rmq[i][j].middle = max(max(rmq[i - 1][S1].middle, rmq[i - 1][S2].middle), rmq[i - 1][S1].right + rmq[i - 1][S2].left);
			rmq[i][j].total = rmq[i - 1][S1].total + rmq[i - 1][S2].total;
		}
}

inline long long make(int X, int Y) {
	int dif = Y - X + 1, aux = 0;
	int v[LMax]; v[0] = 0;
	while (dif) {
		if (dif % 2)
			v[++v[0]] = aux;
		dif /= 2;
		aux++;
	}
	
	RMQ interval = rmq[v[1]][X];
	X += (1 << v[1]);
	
	for (int i = 2; i <= v[0]; i++) {
		RMQ _interval = rmq[v[i]][X], _new;
		
		_new.left = max(interval.left, interval.total + _interval.left);
		_new.right = max(_interval.right, _interval.total + _interval.right);
		_new.middle = max(max(interval.middle, _interval.middle), interval.right + _interval.left);
		_new.total = interval.total + _interval.total;
		interval = _new;
		X += (1 << v[i]);
	}
	return interval.middle;
}

void write() {
	for (int i = 1; i <= M; i++) {
		int X, Y;
		fin >> X >> Y;
		fout << make(X, Y) << '\n';
	}
	fin.close();
	fout.close();
}



int main() {
	read(); solve(); write();
}