# include <cstdio>
# include <algorithm>
# define INF -2000000000
# define fiu_st (nod<<1)
# define fiu_dr ((nod<<1)+1)
# define mij ((st+dr)>>1)
# define N 100010
# define T 250000
using namespace std;
struct arb
{
long long st,dr,sum,best;
} t[T],sol;
int a[N];
int i,n,m,x,y;
inline arb compute(arb x, arb y)
{
if(x.best==INF) return y;
if(y.best==INF) return x;
arb t;
t.sum=x.sum+y.sum;
t.best=max(x.dr+y.st, max(x.best,y.best));
t.st=max(x.st, x.sum+y.st);
t.dr=max(y.dr, y.sum+x.dr);
return t;
}
inline void build(int nod, int st, int dr)
{
if(st==dr)
{
t[nod].st=t[nod].dr=t[nod].sum=t[nod].best=a[st];
return;
}
build(fiu_st,st,mij);
build(fiu_dr,mij+1,dr);
t[nod]=compute(t[fiu_st], t[fiu_dr]);
}
inline arb query(int nod, int st, int dr, int x, int y)
{
if(x<=st && dr<=y) return t[nod];
if(st!=dr)
{
arb q1,q2;
q1.best=q2.best=INF;
if(x<=mij) q1=query(fiu_st,st,mij,x,y);
if(y>mij) q2=query(fiu_dr,mij+1,dr,x,y);
return compute(q1,q2);
}
}
int main()
{
freopen("sequencequery.in", "r", stdin);
freopen("sequencequery.out", "w", stdout);
scanf("%d %d\n", &n, &m);
for(i=1; i<=n; ++i) scanf("%d\n", &a[i]);
build(1,1,n);
while(m--)
{
scanf("%d %d\n", &x, &y);
sol=query(1,1,n,x,y);
printf("%lld\n", sol.best);
}
fclose(stdin);
fclose(stdout);
return 0;
}