#include <fstream>

const int INF = 0x7fffffff;
const int NEG_INF = -0x80000000;

struct node {
    int min, max, maxStart, maxPos, startMax;
};

int n, m, minA, minB, a, b, pos, val, start;

node tree[1 << 18];

inline void update(int p, int st, int dr) {
    if (st == dr) {
        tree[p].min = tree[p].max = val;
        tree[p].maxPos = st;
        tree[p].startMax = tree[p].maxStart = start;
        return;
    }
    int m = (st + dr) / 2, left = 2 * p, right = 2 * p + 1;
    if (pos <= m) update(left, st, m);
    else update(right, m + 1, dr);
    if (tree[left].max > tree[right].max) {
        tree[p].max = tree[left].max;
        tree[p].maxPos = tree[left].maxPos;
        tree[p].maxStart = tree[left].maxStart;
    } else {
        tree[p].max = tree[right].max;
        tree[p].maxPos = tree[right].maxPos;
        tree[p].maxStart = tree[right].maxStart;
    }
    tree[p].min = std::min(tree[left].min, tree[right].min);
    tree[p].startMax = std::max(tree[left].startMax, tree[right].startMax);
}

inline void update(int position, int value) {
    pos = position;
    val = value;
    update(1, 1, n);
}

inline int queryMin(int p, int st, int dr) {
    if (minA <= st && dr <= minB) return tree[p].min;
    int m = (st + dr) / 2, r1 = INF, r2 = INF;
    if (minA <= m) r1 = queryMin(2 * p, st, m);
    if (minB > m) r2 = queryMin(2 * p + 1, m + 1, dr);
    return std::min(r1, r2);
}

inline int queryMin(int st, int dr) {
    minA = st;
    minB = dr;
    return queryMin(1, 1, n);
}

inline int query(int p, int st, int dr) {
    if (a <= st && dr <= b) {
        if (a <= tree[p].maxStart) return tree[p].max;
        else if (tree[p].startMax < a) return tree[p].max - queryMin(a - 1, tree[p].maxPos - 1);
    }
    int m = (st + dr) / 2, r1 = NEG_INF, r2 = NEG_INF;
    if (a <= m) r1 = query(2 * p, st, m);
    if (b > m) r2 = query(2 * p + 1, m + 1, dr);
    return std::max(r1, r2);
}

int main() {
    std::ifstream in("sequencequery.in");
    std::ofstream out("sequencequery.out");
    int i, x, prev = 0;
    in >> n >> m;
    for (i = 1; i <= n; ++i) {
        in >> x;
        if (prev > 0) x += prev;
        else start = i;
        prev = x;
        update(i, x);
    }
    for (i = 0; i < m; ++i) {
        in >> a >> b;
        out << query(1, 1, n) << '\n';
    }
    return 0;
}