#include <bits/stdc++.h>
#define DIM 100001
#define int long long
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
struct nod{
int pref, suff, sum, answer, size;
};
vector <nod> wmt(4 * DIM);
nod Combine(nod st, nod dr){
nod answer;
answer.size = st.size + dr.size;
answer.sum = st.sum + dr.sum;
answer.pref = max(st.pref, st.sum + dr.pref);
answer.suff = max(dr.suff, dr.suff + dr.sum);
answer.answer = max(st.answer,
max(dr.answer,
max(
max(answer.pref, answer.suff), st.suff + dr.pref)));
return answer;
}
void Build_Tree(int node, int st, int dr){
if(st == dr){
fin >> wmt[node].answer;
wmt[node].pref = wmt[node].answer;
wmt[node].suff = wmt[node].answer;
wmt[node].sum = wmt[node].answer;
wmt[node].size = 1;
}
else {
int mij = (st + dr) >> 1;
Build_Tree(node << 1, st, mij);
Build_Tree(node << 1 | 1, mij + 1, dr);
wmt[node] = Combine(wmt[node << 1], wmt[node << 1 | 1]);
}
}
nod INF;
nod Query(int node, int st, int dr, int a, int b){
if(dr < a || st > b)
return INF;
if(st >= a && dr <= b)
return wmt[node];
else {
int mij = (st + dr) >> 1;
nod ok1 = Query(node << 1, st, mij, a, b);
nod ok2 = Query(node << 1 | 1, mij + 1, dr, a, b);
return Combine(ok1, ok2);
}
}
int n, i, Q, st, dr, task;
int32_t main(){
INF.answer = -10e9;
INF.pref = -10e9;
INF.suff = -10e9;
INF.size = 1e9;
fin >> n >> Q;
Build_Tree(1, 1, n);
while(Q--){
fin >> st >> dr;
fout << Query(1, 1, n, st, dr).answer << "\n";
}
fin.close();
fout.close();
return 0;
}