#include <fstream>
using namespace std;

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

const int N = 1e5 + 5;

typedef long long u64;
const u64 oo = -1e15;

u64 A[N * 4], B[N * 4], C[N * 4], S[N * 4], sol, res;
int n, m, v[N];

void build(int node, int lo, int hi) {
    if (lo == hi) {
        A[node] = B[node] = C[node] = S[node] = v[lo];
        return;
    }
    int mid = (lo + hi) >> 1, fiu = node << 1;
    build(fiu, lo, mid);
    build(fiu + 1, mid + 1, hi);
    A[node] = max (A[fiu], S[fiu] + A[fiu + 1]);
    B[node] = max (B[fiu + 1], S[fiu + 1] + B[fiu]);
    C[node] = max (B[fiu] + A[fiu + 1], max(C[fiu], C[fiu + 1]));
    S[node] = S[fiu] + S[fiu + 1];
}

void query(int node, int lo, int hi, int lt, int rt) {
    if (rt < lo || hi < lt)
        return;
    if (lt <= lo && hi <= rt) {
        sol = max(sol, max(res + A[node], C[node]));
        res += max(res + S[node], B[node]);
        return;
    }
    int mid = (lo + hi) >> 1, fiu = node << 1;
    if (lt <= mid)
        query(fiu, lo, mid, lt, rt);
    if (rt > mid)
        query(fiu + 1, mid + 1, hi, lt, rt);
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    build(1, 1, n);
    for (int x, y, i = 0; i < m; ++i) {
        fin >> x >> y;
        sol = oo;
        res = 0;
        query(1, 1, n, x, y);
        fout << sol << "\n";
    }
}