#include <stdio.h>
#include <values.h>
#define Nmax 100001

struct nod { int st, dr, all, sum; } tree[Nmax * 3 + 666];
int v[Nmax]; 
int N, M, x, i, j, rez, S, rst, rdr;


void buildTree(int st, int dr, int loc);
int query(int st, int dr);
inline int max(int x, int y) { return x > y ? x : y; }

int main()
{
	freopen("sequencequery.in", "r", stdin);
	freopen("sequencequery.out", "w", stdout);
	for (scanf("%d %d\n", &N, &M), i = 1; i<=N; i++)
		scanf("%d ", v+i);
	buildTree(1,N,1);
	for (; M; M--)
	{
		scanf("%d %d\n", &i, &j);
		rez = rst = rdr = -MAXINT+1000;
		S = 0;
		query(i,j);
		printf("%d\n", rez);
	}
	return 0;
}

void buildTree(int st, int dr, int loc)
{
	if (st == dr)
	{
		tree[loc].st = tree[loc].dr = tree[loc].all = tree[loc].sum = v[st];
		return;
	}
	int m = (st + dr) >> 1;
	buildTree(st,m,loc<<1);
	buildTree(m+1,dr,(loc<<1) + 1);
	tree[loc].sum = tree[loc << 1].sum + tree[(loc << 1) + 1].sum;
	tree[loc].st = max(tree[loc << 1].st, tree[loc << 1].sum + tree[(loc << 1) + 1].st);
	tree[loc].dr = max(tree[(loc << 1) + 1].dr, tree[(loc << 1) + 1].sum + tree[loc << 1].dr);
	tree[loc].all = max(tree[loc << 1].dr + tree[(loc << 1) + 1].st, max(tree[loc << 1].all, tree[(loc << 1) + 1].all));
}

int query(int st, int dr)
{
	if (st > dr) return 0;
	int ST = 1, DR = N, loc = 1, m;
	while (ST != st)
	{
		m = (ST + DR) >> 1;
		if (st <= m)
		{
			loc = loc << 1;
			DR = m;
		}
		else
		{
			loc = (loc << 1) + 1;
			ST = m+1;
		}
	}
	while (DR > dr)
	{
		DR = (ST + DR) >> 1;
		loc = loc << 1;
	}
	rst = max(rst,S+tree[loc].st);
	rdr = max(tree[loc].sum+rdr,tree[loc].dr);
	rez = max(rez, max(tree[loc].all,max(rst,max(tree[loc].dr,max(rdr,tree[loc].st)))));
	S +=tree[loc].sum;
	query(DR+1,dr);
	return 0;
}