#include <fstream>
const std::string programName = "sequencequery";
std::ifstream f(programName + ".in");
std::ofstream g(programName + ".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 left, right, mid, sum;
}St[MAX + 5];
int main() {
    f >> N >> M;
    for (int i = 1; i <= N; ++i)
        f >> v[i];
    Build(1, 1, N);
    for (int i = 1; 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 0x0;
}
void Build(int node, int left, int right) {
    if (left == right) {
        St[node].left = v[left];
        St[node].right = v[left];
        St[node].mid = v[left];
        St[node].sum = v[left];
        return;
    }
    int mid = (left + right) / 2, leftSon = 2 * node, rightSon = leftSon + 1;
    Build(leftSon, left, mid);
    Build(rightSon, mid + 1, right);
    St[node].sum = St[leftSon].sum + St[rightSon].sum;
    St[node].left = std::max(St[leftSon].left, St[leftSon].sum + St[rightSon].left);
    St[node].right = std::max(St[rightSon].right, St[leftSon].right + St[rightSon].sum);
    St[node].mid = std::max(std::max(St[leftSon].mid, St[rightSon].mid), St[leftSon].right + St[rightSon].left);
}
void query(int node, int left, int right, int queryL, int queryR, int64_t& best, int64_t& answer) {
    if (queryR < left or right < queryL)
        return;
    if (queryL <= left and right <= queryR) {
        answer = std::max(answer, std::max(St[node].mid, best + St[node].left));
        best = std::max(best + St[node].sum, St[node].right);
        return;
    }
    int mid = (left + right) / 2, leftSon = 2 * node, rightSon = leftSon + 1;
    query(leftSon, left, mid, queryL, queryR, best, answer);
    query(rightSon, mid + 1, right, queryL, queryR, best, answer);
}