#include <fstream>
#define ll long long
using namespace std;
const int Nmax = 100000;
int v[Nmax];
struct arbore_intervale{
ll val;
ll prefix;
ll sufix;
ll sum;
};
arbore_intervale aint[4 * Nmax];
void build(int nod, int st, int dr){
if(st == dr){
aint[nod].val = v[st];
aint[nod].prefix = v[st];
aint[nod].sufix = v[st];
aint[nod].sum = v[st];
return;
}
int mid = (st + dr) / 2;
int vecinSt = 2 * nod, vecinDr = 2 * nod + 1;
build(vecinSt, st, mid);
build(vecinDr, mid + 1, dr);
aint[nod].val = max(aint[vecinSt].val, aint[vecinDr].val);
aint[nod].val = max(aint[nod].val, aint[vecinSt].sufix + aint[vecinDr].prefix);
aint[nod].sum = aint[vecinSt].sum + aint[vecinDr].sum;
aint[nod].prefix = max(aint[vecinSt].prefix, aint[vecinSt].sum + aint[vecinDr].prefix);
aint[nod].sufix = max(aint[vecinDr].sufix, aint[vecinDr].sum + aint[vecinSt].sufix);
}
arbore_intervale query(int nod, int st, int dr, int a, int b){
if(st == a && dr == b){
return aint[nod];
}
int mid = (st + dr) / 2;
if(b <= mid){
return query(2 * nod, st, mid, a, b);
}
else if(mid < a){
return query(2 * nod + 1, mid + 1, dr, a, b);
}
else{
arbore_intervale sol, vecinSt, vecinDr;
vecinSt = query(2 * nod, st, mid, a, mid);
vecinDr = query(2 * nod + 1, mid + 1, dr, mid + 1, b);
sol.val = max(vecinSt.val, vecinDr.val);
if(vecinSt.sufix + vecinDr.prefix >= sol.val){
sol.val = vecinSt.sufix + vecinDr.prefix;
}
sol.sum = vecinSt.sum + vecinDr.sum;
sol.prefix = max(vecinSt.prefix, vecinSt.sum + vecinDr.prefix);
sol.sufix = max(vecinDr.sufix, vecinDr.sum + vecinSt.sufix);
return sol;
}
}
int main(){
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int n, m, a, b;
fin >> n >> m;
for(int i = 0; i < n; i++){
fin >> v[i];
}
build(1, 0, n - 1);
for(int i = 0; i < m; i++){
fin >> a >> b;
a--; b--;
fout << query(1, 0, n - 1, a, b).val << '\n';
}
return 0;
}