#include <cstdio>
#define INF "sequencequery.in"
#define OUF "sequencequery.out"
#define SEGT 262144
using namespace std;

struct snod
{
	long long sum,bl,br,best;
}seg[SEGT];
int a,b,c,d;
long long x;

inline long long max(long long f,long long g)
{
	if(f>g) return f;
	else return g;
}

void insert(int nod,int st,int dr)
{
	if(a<=st&&dr<=b) seg[nod].sum=seg[nod].best=seg[nod].bl=seg[nod].br=x;
	else
	{
		int mij=(st+dr)/2;
		if(a<=mij) insert(2*nod,st,mij);
		if(b>mij) insert(2*nod+1,mij+1,dr);
		seg[nod].sum+=x;
		seg[nod].bl=max(seg[2*nod].sum+seg[2*nod+1].bl,seg[2*nod].bl);
		seg[nod].br=max(seg[2*nod].br+seg[2*nod+1].sum,seg[2*nod+1].br);
		seg[nod].best=max(seg[2*nod].best,seg[2*nod+1].best);
		seg[nod].best=max(seg[nod].best,seg[2*nod].br+seg[2*nod+1].bl);
	}
}


long long best_right(int nod,int st,int dr)
{
	if(c<=st&&dr<=d) return seg[nod].br;
	else 
	{
		int mij;
		mij=(st+dr)/2;
		if(c<=mij&&d>mij)
		{
			long long drs;
			drs=best_right(2*nod,st,mij);
			return max(drs+seg[2*nod+1].sum,seg[2*nod+1].br);
		}
		if(c<=mij) return best_right(2*nod,st,mij);
		if(d>mij) return best_right(2*nod+1,mij+1,dr);
	}
}

long long best_left(int nod,int st,int dr)
{
	if(c<=st&&dr<=d) return seg[nod].bl;
	else
	{
		int mij;
		mij=(st+dr)/2;
		if(c<=mij&&d>mij)
		{
			long long sts;
			sts=best_left(2*nod+1,mij+1,dr);
			return max(seg[2*nod].bl,seg[2*nod].sum+sts);
		}
		if(c<=mij) return best_left(2*nod,st,mij);
		if(d>mij) return best_left(2*nod+1,mij+1,dr);
	}
}
	

long long query(int nod,int st,int dr)
{
	if(a<=st&&dr<=b) return seg[nod].best;
	else
	{
	    int mij=(st+dr)/2;
	    if(a<=mij&&b>mij)
	    {
		    long long bst,bdr,lsum,rsum,rez;
		    bst=query(2*nod,st,mij);
		    bdr=query(2*nod+1,mij+1,dr);
		    c=a;d=mij;	
		    rsum=best_right(2*nod,st,mij);
		    c=mij+1;d=b;
		    lsum=best_left(2*nod+1,mij+1,dr);
		    rez=max(bst,bdr);
		    return max(rez,lsum+rsum);
	    }
	    if(a<=mij) return query(2*nod,st,mij);
	    if(b>mij) return query(2*nod+1,mij+1,dr);
	}
}

int main()
{
	FILE *in,*out;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	int i,n,m;
	fscanf(in,"%d %d",&n,&m);
	for(i=1;i<=n;++i)
	{
		a=b=i;
		fscanf(in,"%lld",&x);
		insert(1,1,n);
	}
	for(i=1;i<=m;++i)
	{
		fscanf(in,"%d %d",&a,&b);
		fprintf(out,"%lld\n",query(1,1,n));
	}
	fclose(in);fclose(out);
	return 0;
}