#include <bits/stdc++.h>

using namespace std;

#define INFILE "sequencequery.in"
#define OUTFILE "sequencequery.out"

typedef long long ll;

const int MAX_N = 1e5 + 5;

struct Node {
    ll value;
    ll pref;
    ll suff;
    ll sum;

    Node() {}
    Node(int _value, int _pref, int _suff, int _sum) : value(_value), pref(_pref), suff(_suff), sum(_sum) {}

};

Node aint[MAX_N * 4];

Node helper(Node a, Node b){
    Node aux;
    aux.sum = a.sum + b.sum;
    aux.pref = max(a.pref, a.sum + b.pref);
    aux.suff = max(b.suff, b.sum + a.suff);
    aux.value = max(max(a.value, b.value), a.suff + b.pref);
    return aux;
}

void build(int node, int left, int right){
    if(left == right){
        cin >> aint[node].sum;
        aint[node].pref = aint[node].sum;
        aint[node].suff = aint[node].sum;
        aint[node].value = aint[node].sum;
        return;
    }
    int middle = (left + right) / 2;
    build(2 * node, left, middle);
    build(2 * node + 1, middle + 1, right);
    aint[node] = helper(aint[2 * node], aint[2 * node + 1]);
}

Node query(int node, int left, int right, int x, int y){
    
    if(x <= left && right <= y) return aint[node];

    int middle = (left + right) / 2;

    if(y <= middle) return query(2 * node, left, middle, x, y);
    else if(x > middle) return query(2 * node + 1, middle + 1, right, x, y);

    Node aux1 = query(2 * node, left, middle, x, y);
    Node aux2 = query(2 * node + 1, middle + 1, right, x, y);

    return helper(aux1, aux2);

}

void solve(){

    int n, queries;
    cin >> n >> queries;

    build(1, 1, n);

    for(int i = 0; i < queries; ++i){

        int left, right; cin >> left >> right;

        cout << query(1, 1, n, left, right).value << '\n';

    }

}

int main(){
    ios_base::sync_with_stdio(false);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}