#include <cstdio>
#include <algorithm>
#define FIN "maxq.in"
#define FOUT "maxq.out"
#include <vector>
#include <algorithm>
#define NM 200100
using namespace std;
#define max(a, b) ((a) > (b) ? (a) : (b))
int N, M;
int v[NM];
long long A[4*NM], B[4*NM], C[4*NM], Sum[4*NM];
int ThePosition, TheValue;
void build(int E, int Left, int Right){
if (Left == Right) {
A[E] = B[E] = C[E] = max(v[Left], 0);
Sum[E] = v[Left];
return;
}
int Middle=(Left+Right)>>1,left=E<<1,right=left+1;
build(left,Left,Middle);
build(right, Middle+1,Right);
A[E] = max(A[left], Sum[left]+A[right]);
B[E] = max(B[left]+Sum[right], B[right]);
C[E] = max(max(C[left], C[right]), B[left]+A[right]);
Sum[E] = Sum[left]+Sum[right];
}
void update(int E, int Left, int Right){
if (Left == Right) {
A[E] = B[E] = C[E] = max(TheValue, 0);
Sum[E] = TheValue;
return;
}
int Middle=(Left+Right)>>1,left=E<<1,right=left+1;
if (ThePosition <= Middle)
update(left,Left,Middle);
else
update(right, Middle+1,Right);
A[E] = max(A[left], Sum[left]+A[right]);
B[E] = max(B[left]+Sum[right], B[right]);
C[E] = max(max(C[left], C[right]), B[left]+A[right]);
Sum[E] = Sum[left]+Sum[right];
}
int Start, Finish;
int ans, S;
void query(int E, int Left, int Right){
if (Start <= Left && Right <= Finish) {
if (S < 0)
S = 0;
ans = max(ans, max(S+A[E], C[E]));
S = max(S+Sum[E], B[E]);
return;
}
int Middle=(Left+Right)>>1;
if (Start <= Middle) query(E<<1,Left,Middle);
if (Middle < Finish) query((E<<1)|1, Middle+1,Right);
}
class rmq{
private:
int n,i;
vector< vector <int> > arb;
vector<int> logx;
void logar(){
int i,x=1,y=0;
for (i=1;i<=n;++i){
if (i<(x<<1))
logx[i]=y;
else{
x<<=1;
logx[i]=++y;
}
}
}
public:
void build(vector<int> param,int (*comparator)(int a,int b)){
int i,j,log;
n=param.size()-1;
arb.resize(n+2);
logx.resize(n+2);
logar();
for (log=0;(1<<log)<=n;++log);
for (i=1;i<=n;++i){
arb[i].resize(log+2,0);
arb[i][0]=param[i];
}
for (i=n;i;--i)
for (j=1;i+(1<<j)<=n+1;++j)
arb[i][j]=comparator(arb[i][j-1],arb[i+(1<<(j-1))][j-1]);
}
int query(int a,int b,int (*comparator)(int a,int b)){
int log;
log=logx[b-a+1];
return comparator(arb[a][log],arb[b-(1<<log)+1][log]);
}
};
rmq R;
int cmp(int a,int b){
return max(a,b);
}
vector<int> aa;
int main(){
int i, t, v1, v2;
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out", "w", stdout);
scanf("%d%d", &N, &M);
aa.push_back(0);
for (i = 1; i <= N; ++i){
scanf("%d", &v[i]);
aa.push_back(v[i]);
}
build(1,1,N);
R.build(aa,cmp);
while (M--) {
scanf("%d %d", &v1, &v2);
S = ans = 0;
Start = v1;
Finish = v2;
query(1, 1, N);
if (ans==0)
printf("%lld\n",R.query(v1,v2,cmp));
else
printf("%lld\n", ans);
}
return 0;
}