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

struct info_interval{
	int suma_max, suma_max_st, suma_max_dr, suma_tot;
	info_interval():
		suma_max(0), suma_max_st(0), suma_max_dr(0), suma_tot(0){}
	info_interval(const int x):
		suma_max(x), suma_max_st(x), suma_max_dr(x), suma_tot(x){} };

info_interval join(const info_interval& st, const info_interval& dr){
	info_interval rez(0);
	rez.suma_tot = st.suma_tot + dr.suma_tot;
	rez.suma_max_st = max(st.suma_max_st, st.suma_tot + dr.suma_max_st);
	rez.suma_max_dr = max(dr.suma_max_dr, dr.suma_tot + st.suma_max_dr);
	rez.suma_max =
		max({st.suma_max, dr.suma_max, st.suma_max_dr + dr.suma_max_st});
	return rez; }

class aint{
	const int n;
	vector<info_interval> buf;
public:
	explicit aint(const vector<int>& v):
		n(v.size()), buf(2*n){
		for(int i = n; i < 2*n; ++i){
			buf[i] = info_interval(v[i-n]); }

		for(int i = n-1; i > 0; --i){
			buf[i] = join(buf[2*i], buf[2*i + 1]); } }
	info_interval query(int st, int dr){
		info_interval rez_st(-100001), rez_dr(-100001);
		for(st += n-1, dr += n; st < dr; st /= 2, dr /= 2){
			if(st%2 == 1){
				rez_st = join(rez_st, buf[st++]); }
			if(dr%2 == 1){
				rez_dr = join(buf[--dr], rez_dr); } }
		return join(rez_st, rez_dr); } };

int main(){
	ifstream f("sequencequery.in");
	ofstream g("sequencequery.out");
	int n, m;
	f >> n >> m;
	vector<int> v(n);
	for(auto& x : v){
		f >> x; }
	aint a(v);
	for(int i = 0, st, dr; i < m; ++i){
		f >> st >> dr;
		g << a.query(st, dr).suma_max << '\n'; }
	return 0; }