#include <fstream>
#include <iomanip>
#include <string>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <string.h>
#include <queue>
#include <stack>

#define INF 0x3f3f3f3f

using namespace std;

#ifdef DEBUG
string name = "data";
#else
string name = "sequencequery";
#endif

ifstream fin(name + ".in");
ofstream fout(name + ".out");

#define MAXN 262148

struct Node {
    int64_t beginning;
    int64_t contained;
    int64_t ending;
    int64_t sum;
    
    int64_t best() {
        return max(max(beginning, contained), ending);
    }
};

Node mergeNodes(Node left, Node right) {
    int64_t beginning = max(left.beginning, left.sum + right.beginning);
    
    int64_t ending = max(right.ending, left.ending + right.sum);
    
    int64_t contained = max(max(max(max(left.contained, right.contained), beginning), ending), left.ending + right.beginning);
    
    int64_t sum = -INF;
    
    if (left.sum != -INF && right.sum != -INF) {
        sum = left.sum + right.sum;
    }
    
    return {beginning, contained, ending , sum};
}

Node aint[MAXN];
int n, q;

struct Interval {
    int a;
    int b;
    
    bool equals(Interval &other) {
        return a == other.a && b == other.b;
    }

    bool contains(Interval &other) {
        return other.a >= a && other.b <= b;
    }
    
    bool isDisjoint(Interval &other) {
        return b < other.a || a > other.b;
    }
    
    bool isUnitLength() {
        return a == b;
    }
    
    pair<Interval, Interval> splitAtMidPoint() {
        int mid = (a + b) / 2;
        return {{a, mid}, {mid + 1, b}};
    }
};

Node update(Interval q, Interval window, int node, int x) {
    if (q.isDisjoint(window)) {
        return aint[node];
    }
    
    if (window.isUnitLength()) {
        aint[node] = {x, x, x, x};
        return aint[node];
    }
    
    auto split = window.splitAtMidPoint();
    
    auto left = update(q, split.first, node * 2, x);
    auto right = update(q, split.second, node * 2 + 1, x);
    
    aint[node] = mergeNodes(left, right);
    
    return aint[node];
}

void update(int i, int x) {
    update({i, i}, {1,n}, 1, x);
}

Node query(Interval q, Interval window, int node) {
    if (q.isDisjoint(window)) {
        return {-INF, -INF, -INF, -INF};
    }
    
    if (q.contains(window)) {
        return aint[node];
    }
    
    auto split = window.splitAtMidPoint();
    
    auto left = query(q, split.first, node * 2);
    auto right = query(q, split.second, node * 2 + 1);
    
    return mergeNodes(left, right);
}

int64_t query(int a, int b) {
    auto q = query({a,b}, {1,n}, 1);
    return q.best();
}

int main() {
    
    fin >> n >> q;
    
    for (int i = 1; i <= 2 * n; ++i) {
        aint[i] = {-INF, -INF, -INF, -INF};
    }
    
    for (int i = 1; i <= n; ++i) {
        int x;
        fin >> x;
        update(i, x);
    }
    
    for (int i = 0; i < q; ++i) {
        int x, y;
        fin >> x >> y;
        fout << query(x, y) << "\n";
    }
    
    return 0;
}