#include <bits/stdc++.h>

using namespace std;

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

#define int long long

struct SegmentTree
{
	int to_left;
	int best;
	int to_right;
	int all;
};

const int DIM = 1e5 + 7;
const int INF = 1LL * 1e9 * 1e8;

int v[DIM];

SegmentTree arb[DIM * 4];

void getSums(int nod)
{
	arb[nod].to_right = max(arb[nod * 2 + 1].to_right, arb[nod * 2 + 1].all + arb[nod * 2].to_right);
	arb[nod].to_left = max(arb[nod * 2].to_left, arb[nod * 2].all + arb[nod * 2 + 1].to_left);
	arb[nod].all = arb[nod * 2].all + arb[nod * 2 + 1].all;
	arb[nod].best = arb[nod].all;
	arb[nod].best = max(arb[nod].best, arb[nod].to_left);
	arb[nod].best = max(arb[nod].best, arb[nod].to_right);
	arb[nod].best = max(arb[nod].best, arb[nod * 2].best);
	arb[nod].best = max(arb[nod].best, arb[nod * 2 + 1].best);
	arb[nod].best = max(arb[nod].best, arb[nod * 2].to_right + arb[nod * 2 + 1].to_left);
}

void atrib(int nod, int val)
{
	arb[nod].to_left = val;
	arb[nod].to_right = val;
	arb[nod].all = val;
	arb[nod].best = val;
}

void build(int pos, int l, int r)
{
	if(l == r)
	{
		atrib(pos, v[l]);
		
		return ;
	}
	
	int mid = (l + r) / 2;
	
	build(pos * 2, l, mid);
	build(pos * 2 + 1, mid + 1, r);
	
	getSums(pos);
}

void update(int pos, int l, int r, int x, int val)
{
	if(l == r)
	{
		atrib(pos, val);
		return ;
	}
	
	int mid = (l + r) / 2;
	
	if(x <= mid)
		update(pos * 2, l, mid, x, val);
	
	if(x > mid)
		update(pos * 2 + 1, mid + 1, r, x, val);
	
	getSums(pos);
}

int sol;
int dr;

void query(int pos, int l, int r, int x, int y)
{
	if(x <= l && r <= y)
	{
		sol = max(sol, arb[pos].best);
		
		if(dr == -INF)
		{
			dr = arb[pos].to_right;
		}
		else
		{
			sol = max(sol, dr + arb[pos].to_left);
			dr = max({0LL, dr + arb[pos].all, arb[pos].to_right});
		}
		
		return ;
	}
	
	int mid = (l + r) / 2;
	
	int ans = -INF;
	
	if(x <= mid)
		query(pos * 2, l, mid, x, y);
	
	if(y > mid)
		query(pos * 2 + 1, mid + 1, r, x, y);
}

main()
{
	int n, q;
	fin >> n >> q;
	
	for(int i = 1; i <= n; i++)
		fin >> v[i];
	
	build(1, 1, n);
	
	while(q--)
	{
		int a, b;
		fin >> a >> b;
		
		sol = -INF;
		dr = -INF;
		
		query(1, 1, n, a, b);
		
		fout << sol << '\n';
	}
}