#include<stdio.h>
#define nmax 100002
struct arbore
{
	int s,max,st,dr;
};
int n,m;
int v[nmax];
arbore a[1<<18];
long long suma,maxim;

inline int max(int a, int b){return a>b?a:b;}

void init(int nod, int st, int dr)
{
	int left=nod<<1;
	int right=left|1;
	int m=(st+dr)>>1;
	if(st==dr)
	{
		a[nod].s=a[nod].max=a[nod].st=a[nod].dr=v[st];
		return;
	}
	init(left,st,m);
	init(right,m+1,dr);
	a[nod].s=a[left].s+a[right].s;
	a[nod].max=max(max(a[left].max,a[right].max),a[left].dr+a[right].st);
	a[nod].st=max(a[left].st,a[left].s+a[right].st);
	a[nod].dr=max(a[right].dr,a[right].s+a[left].dr);
}

void query(int nod, int st, int dr, int left, int right)
{
	long long rez=0;
	if(left<=st && dr<=right)
	{
		rez=a[nod].max;
		if(suma+a[nod].st>rez)
			rez=suma+a[nod].st;
		if(suma+a[nod].s>a[nod].dr)
			suma+=a[nod].s;
		else
			suma=a[nod].dr;
		if(rez>maxim)
			maxim=rez;
		return;
	}
	int m=(st+dr)>>1;
	if(left<=m)
		query(nod<<1,st,m,left,right);
	if(m<right)
		query((nod<<1)|1,m+1,dr,left,right);
}

int main()
{
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	scanf("%d%d",&n,&m);
	int i,st,dr;
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	init(1,1,n);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&st,&dr);
		suma=0;
		maxim=(long long)-100000*100000;
		query(1,1,n,st,dr);
		printf("%lld\n",maxim);
	}
	return 0;
}