#include <bits/stdc++.h>
#define leftChild(x) (2 * x)
#define rightChild(x) (2 * x + 1)
#define ll long long
using namespace std;
const ll NMax = 600003;
const ll INF = (1LL << 62);
#define DIM 10000
char buffer[DIM];
ll poz = 0;
void cit(ll &numar){
numar = 0;
char semn = '+';
while(buffer[poz] < '0' || buffer[poz] > '9'){
semn = buffer[poz];
if(++poz == DIM){
fread(buffer,sizeof(char),DIM,stdin);
poz = 0;
}
}
while(buffer[poz] >= '0' && buffer[poz] <= '9'){
numar = numar * 10 + buffer[poz] - '0';
if(++poz == DIM){
fread(buffer,sizeof(char),DIM,stdin);
poz = 0;
}
}
if(semn == '-')
numar *= -1;
}
ll n,m,s,sright,x,y;
ll a[NMax],TRmid[NMax],TRleft[NMax],TRright[NMax],SUM[NMax];
void build(ll node, ll l, ll r, ll ind, ll val){
if(l > ind || r < ind){
return;
}
if(l == ind && r == ind){
TRmid[node] = val; ///center
TRleft[node] = val; ///touching left
TRright[node] = val; ///touching right
SUM[node] = val;
return;
}
ll mid = (l + r) / 2;
build(leftChild(node),l,mid,ind,val);
build(rightChild(node),mid + 1,r,ind,val);
ll sumLeft = max(TRleft[leftChild(node)], SUM[leftChild(node)] + TRleft[rightChild(node)]);
ll sumRight = max(TRright[rightChild(node)], SUM[rightChild(node)] + TRright[leftChild(node)]);
ll sumMid = max(max(sumLeft, sumRight), TRright[leftChild(node)] + TRleft[rightChild(node)]);
sumMid = max(max(TRmid[leftChild(node)], TRmid[rightChild(node)]),sumMid);
TRmid[node] = sumMid;
TRleft[node] = sumLeft;
TRright[node] = sumRight;
SUM[node] = SUM[leftChild(node)] + SUM[rightChild(node)];
}
void query(ll node, ll l, ll r, ll a, ll b){
if(l > b || r < a){
return;
}
if(a <= l && r <= b){
s = max(max(sright,s), max(sright + TRleft[node], TRmid[node]));
sright = max(TRright[node], SUM[node] + sright);
return;
}
ll mid = (l + r) / 2;
query(leftChild(node),l,mid,a,b);
query(rightChild(node),mid + 1,r,a,b);
}
int main()
{
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
cit(n);cit(m);
for(ll i = 1; i <= n; ++i){
cit(a[i]);
build(1,1,n,i,a[i]);
}
for(ll i = 1; i <= m; ++i){
cit(x);cit(y);
s = -INF;
sright= -INF;
query(1,1,n,x,y);
ll ans = max(s,sright);
printf("%lld\n",ans);
}
return 0;
}