#include<stdio.h>
#define infile "sequencequery.in"
#define outfile "sequencequery.out"
#define nmax (400*1001)
#define infinit (~(1<<31))
struct arb
{
long long min; //valoarea minima din interval
long long max; //valoarea maxima din interval
long best; //subsecventa de suma maxima
}a[nmax];
long long v[nmax]; //vectorul cu elementele
long long qmin; //valoarea minima la fiecare query
long long inf=(long long)infinit*(long long)infinit; //valoare infinita
int n; //numarul de elemente din arbore
int m; //numarul de query-uri
inline long long min(long long a, long long b)
{
if(a<b) return a; return b;
}
inline long long max(long long a, long long b)
{
if(a>b) return a; return b;
}
void read()
{
int i;
scanf("%d %d\n",&n,&m);
for(i=1;i<=n;i++)
scanf("%lld",&v[i]);
}
void init()
{
int i;
for(i=1;i<=n;i++)
v[i]+=v[i-1];
}
void construct_arb(int rad, int st, int dr)
{
a[rad].best=a[rad].max=-inf; a[rad].min=inf;
if(st==dr)
{
a[rad].best=v[st]-v[st-1];
a[rad].min=v[st-1];
a[rad].max=v[st];
return;
}
int mij=(st+dr)>>1;
construct_arb(rad<<1,st,mij);
construct_arb((rad<<1)|1,mij+1,dr);
a[rad].min=min(a[rad<<1].min,a[(rad<<1)|1].min);
a[rad].max=max(a[rad<<1].max,a[(rad<<1)|1].max);
a[rad].best=max(a[(rad<<1)|1].max-a[rad<<1].min,max(a[rad<<1].best,a[(rad<<1)|1].best));
}
long long query(int rad, int st, int dr, int p, int q)
{
if(p<=st && dr<=q)
{
long long r=a[rad].best;
if(qmin!=inf) r=max(r,a[rad].max-qmin);
qmin=min(qmin,a[rad].min);
return r;
}
int mij=(st+dr)>>1;
if(p<=mij && mij<q)
{
long long r=query(rad<<1,st,mij,p,q);
r=max(r,query((rad<<1)|1,mij+1,dr,p,q));
return r;
}
else if(p<=mij) return query(rad<<1,st,mij,p,q);
else return query((rad<<1)|1,mij+1,dr,p,q);
}
void solve()
{
int st,dr;
while(m--)
{
qmin=inf;
scanf("%d %d\n",&st,&dr);
printf("%lld\n",query(1,1,n,st,dr));
}
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
read();
init();
construct_arb(1,1,n);
solve();
fclose(stdin);
fclose(stdout);
return 0;
}