#include <bits/stdc++.h>

using namespace std;

typedef int64_t i64;
const int NMAX = 100010;
const i64 inf = 0x3f3f3f3f3f3f3f3fLL;

int N, M;
int V[NMAX];

struct Node {
    i64 left, right, smax;
    int lpos, rpos;
} T[4 * NMAX], nil;

Node Combine(const Node &left, const Node &right, int mid) {
    Node ret;

    ret.smax = max(left.smax, right.smax);
    ret.smax = max(ret.smax, left.right + right.left);
    ret.smax = max(ret.smax, max(left.right, max(left.left, max(right.right, right.left))));

    ret.left = -inf;
    if (left.lpos == mid) {
        ret.left = left.left + right.left;
        ret.lpos = right.lpos;
    }

    if (left.left > ret.left) {
        ret.left = left.left;
        ret.lpos  = left.lpos;
    }

    ret.right = -inf;
    if (right.rpos == mid + 1) {
        ret.right = left.right + right.right;
        ret.rpos = left.right;
    }

    if (right.right > ret.right) {
        ret.right = right.right;
        ret.rpos  = right.rpos;
    }

    return ret;
}

void Build(int node, int left, int right) {
    if (left == right) {
        T[node].smax = V[left];
        T[node].left = V[left];
        T[node].right = V[left];
        T[node].lpos = left;
        T[node].rpos = right;
        return;
    }

    int mid = (left + right) / 2;
    Build(node * 2, left, mid);
    Build(node * 2 + 1, mid + 1, right);

    T[node] = Combine(T[node * 2], T[node * 2 + 1], mid);
}

Node Query(int node, int left, int right, int from, int to) {
    if (left >= from && right <= to)
        return T[node];

    if (left >= right)
        return nil;

    int mid = (left + right) / 2;

    Node ret, lt = nil, rt = nil;

    if (from <= mid)
        lt = Query(node * 2, left, mid, from, to);
    if (to > mid)
        rt = Query(node * 2 + 1, mid + 1, right, from, to);

    ret = Combine(lt, rt, mid);
    return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	#ifndef ONLINE_JUDGE
	assert(freopen("sequencequery.in", "r", stdin) != NULL);
    assert(freopen("sequencequery.out", "w", stdout) != NULL);
    assert(freopen("debug.err", "w", stderr) != NULL);
    #endif

    int i, j;
    nil = {-inf, -inf, -inf, -1, -1};

    cin >> N >> M;
    for (i = 1; i <= N; ++i)
        cin >> V[i];

    Build(1, 1, N);

    Node answer;
    while (M--) {
        cin >> i >> j;
        answer = Query(1, 1, N, i, j);
        cout << answer.smax << '\n';
    }

	return 0;
}