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

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


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);
		ok = 0;
		query(i,j);
		printf("%d\n", temp.all);
	}
	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;
	}

	if (!ok) { temp = tree[loc]; ok = 1; }
	else
	{
		temp2.sum = temp.sum + tree[loc].sum;
		temp2.st = max(temp.st, temp.sum + tree[loc].st);
		temp2.dr = max(tree[loc].dr, tree[loc].sum + temp.dr);
		temp2.all = max(temp.dr + tree[loc].st, max(temp.all, tree[loc].all));
		temp = temp2;
	}

	query(DR+1,dr);
	return 0;

}