using namespace std;
#include <algorithm>
#include <cstdio>
#define maxn 100001
#define common \
	int m=(l+r)>>1, L=n<<1, R=L+1
#define ll long long	
ll sum[maxn*3], smax[3*maxn], st[3*maxn],dr[3*maxn];
ll a[maxn];
int n, m;
ll sol, S;

/*
inline ll max(ll a, ll b)
{
	if(a>b) return a;
	return b;
}
inline ll min(ll a, ll b)
{
	if(a<b) return a;
	return b;
}
inline int min(int a, int b)
{
	if(a<b) return a;
	return b;
}
*/



inline void build(int n, int l, int r)
{
	if(l==r)
	{
		sum[n]=smax[n]=st[n]=dr[n]=a[l];
		return;
	}
	common;
	
	build(L, l, m);
	build(R, m+1, r);
	
	sum[n]=sum[L]+sum[R];
	st[n]=max(st[L], sum[L]+st[R]);
	dr[n]=max(dr[R], sum[R]+dr[L]);
	smax[n]=max(sum[n], max(st[n], dr[n]));
	smax[n]=max(smax[n], dr[L]+st[R]);
	smax[n]=max(smax[n], max(smax[L], smax[R]));
	
}

inline void query(int n, int l, int r, int ql, int qr)
{
	if(l==ql && r==qr)
	{
		sol=max(sol, S+st[n]);
		S=max(S+sum[n],dr[n]);
		sol=max(sol, smax[n]);
		sol=max(sol, S);
		
		return;
	}
	
	common;
	
	if(ql<=m) query(L, l, m, ql, min(qr, m));
	if(qr>m)  query(R, m+1, r, max(ql, m+1), qr);
	
}


int main()
{
	int i;
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	scanf("%d %d\n", &n,&m);
	for(i=1;i<=n;++i) scanf("%lld ", a+i);
	
	build(1, 1, n);
	
	int p, q;
	while(m--)
	{
		scanf("%d %d\n", &p, &q);
		sol=S=-10000000000000000LL;
		query(1, 1, n, p, q);
		printf("%lld\n",sol);
	}
	

	return 0;
}