#include <fstream>
std::ifstream f("sequencequery.in");
std::ofstream g("sequencequery.out");
const int MAX = 1e5;
const int64_t INF = 1e18;
int N, M, v[MAX + 5];
void query(int, int, int, int, int, int64_t&, int64_t&);
void Build(int, int, int);
struct{
    int64_t l, r, m, sum;
}St[4 * MAX + 5];
int main(){
    f >> N >> M;
    for(int i = 1; i <= N; ++i)
        f >> v[i];
    Build(1, 1, N);
    for(int i = 0; i < M; ++i){
        int left, right;
        f >> left >> right;
        int64_t best = -INF, answer = -INF;
        query(1, 1, N, left, right, best, answer);
        g << answer << "\n";
    }
    return 0;
}
void Build(int node, int l, int r){
    if(l == r){
        St[node].l = v[l];
        St[node].r = v[l];
        St[node].m = v[l];
        St[node].sum = v[l];
        return;
    }
    int mid = (l + r) / 2, leftSon = 2 * node, rightSon = leftSon + 1;
    Build(leftSon, l, mid);
    Build(rightSon, mid + 1, r);
    St[node].sum = St[leftSon].sum + St[rightSon].sum;
    St[node].l = std::max(St[leftSon].l, St[leftSon].sum + St[rightSon].l);
    St[node].r = std::max(St[rightSon].r, St[leftSon].r + St[rightSon].sum);
    St[node].m = std::max(std::max(St[leftSon].m, St[rightSon].m), St[leftSon].r + St[rightSon].l);
}
void query(int node, int l, int r, int queryL, int queryR, int64_t& best, int64_t& answer){
    if(queryR < l or r < queryL)
        return;
    if(queryL <= l and r <= queryR){
        answer = std::max(answer, std::max(St[node].m, best + St[node].l));
        best = std::max(best + St[node].sum, St[node].r);
        return;
    }
    int mid = (l + r) / 2, leftSon = 2 * node, rightSon = leftSon + 1;
    query(leftSon, l, mid, queryL, queryR, best, answer);
    query(rightSon, mid + 1, r, queryL, queryR, best, answer);
}