#include <iostream>
#include <fstream>
#include <climits>

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

#define NMAX 100000

int v[NMAX + 1];

struct Node {
    long long sum, pref, suf, best;
} seg[4 * NMAX + 5];

Node combine(Node a, Node b) {
    Node c;
    c.sum  = a.sum + b.sum;
    c.pref = max(a.pref, a.sum + b.pref);
    c.suf  = max(b.suf, b.sum + a.suf);
    c.best = max(max(a.best, b.best), a.suf + b.pref);
    return c;
}

void build(int node, int st, int dr) {
    if (st == dr) {
        long long x = v[st];
        seg[node].sum = seg[node].pref = seg[node].suf = seg[node].best = x;
        return;
    }
    int mid = (st + dr) / 2;
    build(node * 2, st, mid);
    build(node * 2 + 1, mid + 1, dr);
    seg[node] = combine(seg[node * 2], seg[node * 2 + 1]);
}

Node query(int node, int st, int dr, int qs, int qd) {
    if (qs <= st && dr <= qd)
        return seg[node];
    int mid = (st + dr) / 2;
    if (qd <= mid)
        return query(node * 2, st, mid, qs, qd);
    if (qs > mid)
        return query(node * 2 + 1, mid + 1, dr, qs, qd);
    Node left  = query(node * 2, st, mid, qs, qd);
    Node right = query(node * 2 + 1, mid + 1, dr, qs, qd);
    return combine(left, right);
}

int main() {
    int N, M;
    fin >> N >> M;
    for (int i = 1; i <= N; i++)
        fin >> v[i];
    build(1, 1, N);
    for (int i = 1; i <= M; i++) {
        int x, y;
        fin >> x >> y;
        fout << query(1, 1, N, x, y).best << '\n';
    }
    return 0;
}