#include <bits/stdc++.h>
 
using namespace std;
 
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
 
struct data {
    long long sum, pref, suff, ans;
} t[400001];
 
int a[100001];
int N, M;
 
data make_data(int val){
    data res;
    res.sum = val;
    res.pref = res.suff = res.ans = val;
    return res;
}
 
data combine(data l, data r){
    data res;
    res.sum = l.sum + r.sum;
    res.pref = max(l.pref, l.sum + r.pref);
    res.suff = max(r.suff, r.sum + l.suff);
    res.ans = max(max(l.ans, r.ans), l.suff + r.pref);
    return res;
}
 
data query(int v, int tl, int tr, int l, int r){
    if(l > r)
        return make_data(INT_MIN);
    if(l == tl && r == tr)
        return t[v];
    int tm = (tl + tr) >> 1;
    return combine(query(v << 1, tl, tm, l, min(r, tm)), query(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r));
}
 
void build(int v, int tl, int tr){
    if(tl == tr)
        t[v] = make_data(a[tl]);
    else{
        int tm = (tl + tr) >> 1;
        build(v << 1, tl, tm);
        build(v << 1 | 1, tm + 1, tr);
        t[v] = combine(t[v << 1], t[v << 1 | 1]);
    }
}
 
void update(int v, int tl, int tr, int pos, int new_val){
    if(tl == tr)
        t[v] = make_data(new_val);
    else{
        int tm = (tl + tr) >> 1;
        if(pos <= tm) update(v << 1, tl, tm, pos, new_val);
        else  update(v << 1 | 1, tm + 1, tr, pos, new_val);
        t[v] = combine(t[v << 1], t[v << 1 | 1]);
    }
}
 
int main(){
    f >> N >> M;
    for(int i = 1;i <= N;i++)
        f >> a[i];
 
    build(1, 1, N);
    while(M--){
        int a, b;
        f >> a >> b;
        g << query(1, 1, N, a, b).ans << "\n";
    }
 
 
}