#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
long long n,m,i,A,B,s,x,v[100002],a[400100],arbs[400100],arbd[400100],as[400100];
void schimba(long i,long st,long dr)
{
    long mij;
    if(st==dr)
        a[i]=as[i]=arbs[i]=arbd[i]=v[st];
    else
    {
        mij=(st+dr)/2;
		schimba(2*i,st,mij);
		schimba(2*i+1,mij+1,dr);
		as[i]=as[2*i]+as[2*i+1];
		arbs[i]=max(arbs[2*i],as[2*i]+arbs[2*i+1]);
		arbd[i]=max(arbd[2*i+1],as[2*i+1]+arbd[2*i]);
		a[i]=max(a[2*i],a[2*i+1]);
		a[i]=max(a[i],arbd[2*i]+arbs[2*i+1]);
    }
}
void detmax(long i,long st,long dr, long A, long B)
{
    long mij;
    if(A<=st&&B>=dr)
    {
		if(s<0)
			s=0;
        if(a[i]>x)
        x=a[i];
		if(s+arbs[i]>x)
			x=s+arbs[i];
		s+=as[i];
		if(arbd[i]>s)
			s=arbd[i];
    }
    else
    {
        mij=(st+dr)/2;
        if(A<=mij)
            detmax(2*i,st,mij,A,B);
            if(mij<B)
            detmax(2*i+1,mij+1,dr,A,B);
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;++i)
        f>>v[i];
	schimba(1,1,n);
    for(i=1;i<=m;++i)
    {
        f>>A>>B;
        s=0;
        x=v[A];
		detmax(1,1,n,A,B);
		g<<x<<"\n";
    }
    return 0;
}