#include <algorithm>
using namespace std;
#define ll long long
#define INF 1LL<<62
#define DIM 100005
#define MAX 10005
ll sum[DIM],Min[3*DIM],Max[3*DIM],best[3*DIM];
char buff[MAX];
int a[DIM];
int n,m,pozitie;
inline void cit (int &nr)
{
char semn='+';
for (nr=0; buff[pozitie]<'0' || buff[pozitie]>'9'; )
{
semn=buff[pozitie];
if (++pozitie==MAX)
{
fread (buff,1,MAX,stdin);
pozitie=0;
}
}
for ( ; '0'<=buff[pozitie] && buff[pozitie]<='9'; )
{
nr=nr*10+buff[pozitie]-'0';
if (++pozitie==MAX)
{
fread (buff,1,MAX,stdin);
pozitie=0;
}
}
if (semn=='-')
nr=-nr;
}
void read ()
{
int i;
cit (n); cit (m);
for (i=1; i<=n; ++i)
{
cit (a[i]);
sum[i]=sum[i-1]+a[i];
}
}
void build (int nod,int st,int dr)
{
int mij;
if (st==dr)
{
best[nod]=a[st];
Max[nod]=sum[st];
Min[nod]=sum[st-1];
}
else
{
mij=(st+dr)/2;
build (2*nod,st,mij);
build (2*nod+1,mij+1,dr);
Max[nod]=max (Max[2*nod],Max[2*nod+1]);
Min[nod]=min (Min[2*nod],Min[2*nod+1]);
best[nod]=max (max (best[2*nod],best[2*nod+1]),Max[2*nod+1]-Min[2*nod]);
}
}
ll qmax (int nod,int st,int dr,int in,int sf)
{
ll nrt=-INF;
int mij;
if (in<=st && dr<=sf)
return Max[nod];
mij=(st+dr)/2;
if (in<=mij)
nrt=max (nrt,qmax (2*nod,st,mij,in,sf));
if (mij<sf)
nrt=max (nrt,qmax (2*nod+1,mij+1,dr,in,sf));
return nrt;
}
ll qmin (int nod,int st,int dr,int in,int sf)
{
ll nrt=INF;
int mij;
if (in<=st && dr<=sf)
return Min[nod];
mij=(st+dr)/2;
if (in<=mij)
nrt=min (nrt,qmin (2*nod,st,mij,in,sf));
if (mij<sf)
nrt=min (nrt,qmin (2*nod+1,mij+1,dr,in,sf));
return nrt;
}
ll query (int nod,int st,int dr,int in,int sf)
{
ll nrt=-INF;
int mij;
if (in<=st && dr<=sf)
return best[nod];
mij=(st+dr)/2;
if (in<=mij)
nrt=max (nrt,query (2*nod,st,mij,in,sf));
if (mij<sf)
nrt=max (nrt,query (2*nod+1,mij+1,dr,in,sf));
if (in<=mij && mij<sf)
nrt=max (nrt,qmax (2*nod+1,mij+1,dr,in,sf)-qmin (2*nod,st,mij,in,sf));
return nrt;
}
void solve ()
{
int i,x,y;
for (i=1; i<=m; ++i)
{
cit (x); cit (y);
printf ("%lld\n",query (1,1,n,x,y));
}
}
int main ()
{
freopen ("sequencequery.in","r",stdin);
freopen ("sequencequery.out","w",stdout);
read ();
build (1,1,n);
solve ();
return 0;
}