#include <stdio.h>
#define inf (int)1e6
#define nmax 100001
#define vmax 300001
struct cell {
int total_sum,sum_left,sum_right,best_sum;
};
int a[nmax],n,m,i,v1,v2;
cell arb[vmax];
inline int max(int a,int b) {
if(a > b) return a;
else return b;
}
void create(int nod,int left,int right) {
if(left == right) arb[nod].total_sum = arb[nod].sum_left = arb[nod].sum_right = arb[nod].best_sum = a[left];
else {
int mi = (left + right) / 2;
create(nod * 2,left,mi);
create(nod * 2 + 1,mi + 1,right);
arb[nod].total_sum = arb[nod * 2].total_sum + arb[nod * 2 + 1].total_sum;
arb[nod].sum_left = max(arb[nod * 2].sum_left,arb[nod * 2].total_sum + arb[nod * 2 + 1].sum_left);
arb[nod].sum_right = max(arb[nod * 2 + 1].sum_right,arb[nod * 2 + 1].total_sum + arb[nod * 2].sum_right);
arb[nod].best_sum = arb[nod].total_sum;
arb[nod].best_sum = max(arb[nod].best_sum,arb[nod * 2].sum_right + arb[nod * 2 + 1].sum_left);
arb[nod].best_sum = max(arb[nod].best_sum,arb[nod * 2].best_sum);
arb[nod].best_sum = max(arb[nod].best_sum,arb[nod * 2 + 1].best_sum);
arb[nod].best_sum = max(arb[nod].best_sum,arb[nod].sum_left);
arb[nod].best_sum = max(arb[nod].best_sum,arb[nod].sum_right);
}
}
cell query(int nod,int st,int dr,int left,int right) {
int mi = 0,p1 = 0,p2 = 0;
cell part1,part2;
part1.total_sum = part1.sum_left = part1.sum_right = part1.best_sum = 0;
part2.total_sum = part2.sum_left = part2.sum_right = part2.best_sum = 0;
if(st >= left && dr <= right) return arb[nod];
else {
mi = (st + dr) / 2;
if(mi >= left) {
p1 = 1;
part1 = query(nod * 2,st,mi,left,right);
}
if(mi < right) {
p2 = 1;
part2 = query(nod * 2 + 1,mi + 1,dr,left,right);
}
cell rez;
rez.total_sum = -inf;
if(p1) rez.total_sum += part1.total_sum;
if(p2) rez.total_sum += part2.total_sum;
rez.sum_left = -inf;
if(p1) rez.sum_left = part1.sum_left;
if(p1 && p2) rez.sum_left = max(rez.sum_left,part1.total_sum + part2.sum_left);
rez.sum_right = -inf;
if(p2) rez.sum_right = part2.sum_right;
if(p1 && p2) rez.sum_right = max(rez.sum_right,part2.total_sum + part1.sum_right);
rez.best_sum = rez.total_sum;
rez.best_sum = max(rez.best_sum,rez.sum_left);
rez.best_sum = max(rez.best_sum,rez.sum_right);
if(p1) rez.best_sum = max(rez.best_sum,part1.best_sum);
if(p2) rez.best_sum = max(rez.best_sum,part2.best_sum);
if(p1 && p2) rez.best_sum = max(rez.best_sum,part1.sum_right + part2.sum_left);
return rez;
}
}
int main() {
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
scanf("%d%d",&n,&m);
for(i = 1; i <= n; i++) scanf("%d",&a[i]);
create(1,1,n);
for(i = 1; i <= m; i++) {
scanf("%d%d",&v1,&v2);
cell ax = query(1,1,n,v1,v2);
printf("%d\n",ax.best_sum);
}
return 0;
}