#pragma once


#include<iostream>
#include<fstream>

using namespace std;


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

#define DIM 400000
#define ElemDIM 100000

class Nod {
public:
	long long intervalSum, leftMax, rightMax, Max;
public:
	Nod() {};
	Nod(int intervalSum, int leftMax, int rightMax, int Max) {
		this->intervalSum = intervalSum;
		this->leftMax = leftMax;
		this->rightMax = rightMax;
		this->Max = Max;
	}
};

long long max(int a, int b) {
	if (a > b)
		return a;
	return b;
}

long long elements[ElemDIM], fSumTotal, fMax, fLeftMax, fRightMax, sSumTotal, sMax, sLeftMax, sRightMax, _inf = -1LL<<62;
Nod aint[DIM];

void build(int nod, int st, int dr) {
	if (st == dr) {
		int val = elements[st];
		aint[nod] = Nod(val, val, val, val);
		return;
	}
	int mid = st + (dr - st) / 2;
	build(2 * nod, st, mid);
	build(2 * nod + 1, mid + 1, dr);

	//sum
	aint[nod].intervalSum = aint[2 * nod].intervalSum + aint[2 * nod + 1].intervalSum;


	// max
	long long maxStandalone = max(aint[2 * nod].Max, aint[2 * nod + 1].Max);
	long long maxConnected = aint[2 * nod].rightMax + aint[2 * nod + 1].leftMax;
	aint[nod].Max = max(maxStandalone, maxConnected);

	// leftMax
	aint[nod].leftMax = max(aint[2 * nod].leftMax, aint[2 * nod].intervalSum + aint[2 * nod + 1].leftMax);

	// rightMax
	aint[nod].rightMax = max(aint[2 * nod + 1].rightMax, aint[2 * nod + 1].intervalSum + aint[2 * nod].rightMax);
}

void query(int nod, int st, int dr, int qStart, int qEnd) {
	if (qStart <= st && qEnd >= dr) {
		if (sMax == _inf) {
			sMax = aint[nod].Max;
			sSumTotal = aint[nod].intervalSum;
			sLeftMax = aint[nod].leftMax;
			sRightMax = aint[nod].rightMax;
		}
		else {
			fSumTotal = sSumTotal + aint[nod].intervalSum;
			long long maxAlone = max(sMax, aint[nod].Max);
			long long maxConnect = sRightMax + aint[nod].leftMax;
			fMax = max(maxAlone, maxConnect);
			fLeftMax = max(sLeftMax, sSumTotal + sLeftMax);
			fRightMax = max(aint[nod].rightMax, aint[nod].intervalSum + sRightMax);

			sMax = fMax;
			sSumTotal = fSumTotal;
			sLeftMax = fLeftMax;
			sRightMax = fRightMax;
		}
		return;
	}
	int mid = st + (dr - st) / 2;
	if (qStart <= mid) {
		query(2 * nod, st, mid, qStart, qEnd);
	}
	if (qEnd > mid) {
		query(2 * nod + 1, mid + 1, dr, qStart, qEnd);
	}

}

int main() {
	int N, M, qStart, qEnd;
	fin >> N >> M;
	for (int i = 1; i <= N; i++) {
		fin >> elements[i];
	}
	build(1, 1, N);
	while (M) {
		fin >> qStart >> qEnd;
		sSumTotal = sMax = sLeftMax = sRightMax = fSumTotal = fMax = fLeftMax = fRightMax = _inf;
		query(1, 1, N, qStart, qEnd);
		if (fMax != _inf)
			fout << fMax << "\n";
		else
			fout << sMax << "\n";
		M--;
	}
	return 0;
}