#include <stdio.h>
#include <vector>
#define NMAX 100005
#define LMAX 1<<18
#define ll long long
#define INF 1LL << 62
int n,m,A[NMAX],a,b,r;
ll B[LMAX],C[LMAX],D[LMAX],E[LMAX],sum[LMAX],rez,val;
void read()
{
scanf("%d%d",&n,&m);
int i;
for (i=1; i<=n; i++)
scanf("%d",&A[i]);
}
inline ll max(ll x,ll y)
{
return x>y ? x : y;
}
void cstr(int nod,int st,int dr)
{
if (st==dr)
{
B[nod]=A[st]; C[nod]=A[st]; D[nod]=A[st]; E[nod]=A[st];
return ;
}
int mij=(st+dr)/2;
cstr(nod*2,st,mij);
cstr(nod*2+1,mij+1,dr);
B[nod]=max(B[2*nod],E[2*nod]+B[2*nod+1]);
C[nod]=max(C[2*nod+1],E[2*nod+1]+C[2*nod]);
D[nod]=max(max(D[2*nod],D[2*nod+1]),C[2*nod]+B[2*nod+1]);
E[nod]=E[2*nod]+E[2*nod+1];
}
void query(int nod,int st,int dr)
{
if (a>dr || b<st)
return;
if (a<=st && dr<=b)
{
rez=max(rez,D[nod]);
rez=max(rez,sum[r]+B[nod]+val);
r++;
sum[r]=sum[r-1]+E[nod];
val=max(val,-sum[r]+C[nod]);
return ;
}
if (st==dr)
return ;
int mij=(st+dr)/2;
query(2*nod,st,mij);
query(2*nod+1,mij+1,dr);
}
void solve()
{
int i;
for (i=1; i<=m; i++)
{
scanf("%d%d",&a,&b);
rez=-INF; r=0; val=0;
query(1,1,n);
printf("%lld\n",rez);
}
}
int main()
{
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
read();
cstr(1,1,n);
solve();
return 0;
}