#include <iostream>
#include <fstream>

using namespace std;

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

const int INF = 1e9;
const int N = 1e5;

int l[4 * N], r[4 * N], sum[4 * N], best[4 * N];

void update(int node, int left, int right, int pos, int val) {
    if (left > right)
        return;
    if (left == right) {
        best[node] = val;
        l[node] = val;
        r[node] = val;
        sum[node] = val;
        return;
    }
    int mid = (left + right) / 2;
    int leftNode = node * 2, rightNode = node * 2 + 1;
    if (pos <= mid)
        update(leftNode, left, mid, pos, val);
    else
        update(rightNode, mid + 1, right, pos, val);
    l[node] = max(l[leftNode], sum[leftNode] + l[rightNode]);
    r[node] = max(r[rightNode], sum[rightNode] + r[leftNode]);
    sum[node] = sum[leftNode] + sum[rightNode];
    best[node] = max(best[leftNode], max(best[rightNode], r[leftNode] + l[rightNode]));
}

int ans, bestInterval;
void query(int node, int left, int right, int ql, int qr) {
    if (left > right)
        return;
    if (ql <= left && right <= qr) {
//        cout << left << ' ' << right << ":\n";
//        cout << l[node] << ' ' << r[node] << '\n';
        ans = max(ans, max(bestInterval + l[node], best[node]));
        bestInterval = max(bestInterval + sum[node], r[node]);
//        cout << ans << ' ' << bestInterval << "\n\n\n";
        return;
    }
    int mid = (left + right) / 2;
    int leftNode = node * 2, rightNode = node * 2 + 1;
    if (ql <= mid)
        query(leftNode, left, mid, ql, qr);
    if (mid < qr)
        query(rightNode, mid + 1, right, ql, qr);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    in >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        in >> x;
        update(1, 1, n, i, x);
    }
    for (int i = 1; i <= m; i++) {
        int ql, qr;
        in >> ql >> qr;
        ans = -INF;
        bestInterval = 0;
        query(1, 1, n, ql, qr);
        out << ans << '\n';
    }

    return 0;
}