#include <iostream>
#include <fstream>
using namespace std;
 
ifstream fin ("sequencequery.in");
ofstream fout ("sequencequery.out");
 
const int maxN = 4e5 + 20;
const int inf = 1e9;

struct nod {
    long long suf, pref, ans, sum;
} t[maxN];

int v[maxN/4];

nod combine(nod l, nod r) {
    nod res;
    res.sum = l.sum + r.sum;
    res.pref = max(l.pref, l.sum + r.pref);
    res.suf = max(r.suf, r.sum + l.suf);
    res.ans = max(max(l.ans, r.ans), l.suf + r.pref);
    return res;
}

void build (int node, int st, int dr) {
    if(st > dr) return ;
    if(st == dr) {
        t[node] = {v[st], v[st], v[st], v[st]}; 
    } else {
        int mij = (st + dr) / 2;
        build(node * 2, st, mij);
        build(node * 2 + 1, mij+1, dr);
        
        t[node] = combine(t[node*2], t[node*2+1]);
    }
}

nod query(int node, int st , int dr, int l, int r) {
    if(l > r) return {-inf,-inf,-inf};
    if(st == l && dr == r) {
        return t[node];
    } 
    int mij = (st + dr) / 2;
    nod t1 = query(node * 2, st, mij, l, min(r,mij));
    nod t2 = query(node * 2 + 1, mij+1, dr, max(l, mij+1), r);
    
    return combine (t1, t2);
}
 
int main()
{
    int n, m; fin >> n >> m;
    
    for(int i = 1; i <= n; ++i)
        fin >> v[i];
    
    build(1, 1, n);
    
    for(int i = 1; i <= m; ++i) {
        int l, r; fin >> l >> r;
        fout << query(1, 1, n, l, r).ans << '\n';
    }
    
    return 0;
}