#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
const int MAXN = 100001;

int arr[MAXN], n, t;

struct Node {
    int sum, pre, suf, sol;
}tree[4 * MAXN];

void createTree(int left, int right, int ind) {
    if (left == right) {
        tree[ind].sol = tree[ind].sum = tree[ind].pre = tree[ind].suf = arr[left];
        return;
    }
    int mid = left + (right - left) / 2;
    createTree(left, mid, 2 * ind);
    createTree(mid + 1, right, 2 * ind + 1);
    tree[ind].sum = tree[2 * ind].sum + tree[2 * ind + 1].sum;
    tree[ind].pre = max(tree[2 * ind].pre, tree[2 * ind].sum + tree[2 * ind + 1].pre);
    tree[ind].suf = max(tree[2 * ind + 1].suf, tree[2 * ind + 1].sum + tree[2 * ind].suf);
    tree[ind].sol = max(tree[2 * ind].sol, tree[2 * ind + 1].sol);
    tree[ind].sol = max(tree[ind].sol, tree[2 * ind].suf + tree[2 * ind + 1].pre);
}

Node findMax(int x, int y, int left, int right, int ind) {
    if (left >= x && right <= y)
        return tree[ind];
    int mid = left + (right - left) / 2;
    if (y <= mid)
        return findMax(x, y, left, mid, 2 * ind);
    if (x > mid)
        return findMax(x, y, mid + 1, right, 2 * ind + 1);
    Node leftRes = findMax(x, y, left, mid, 2 * ind), rightRes = findMax(x, y, mid + 1, right, 2 * ind + 1), res;
    res.sum = leftRes.sum + rightRes.sum;
    res.pre = max(leftRes.pre, leftRes.sum + rightRes.pre);
    res.suf = max(rightRes.suf, rightRes.sum + leftRes.suf);
    res.sol = max(leftRes.sol, rightRes.sol);
    res.sol = max(res.sol, leftRes.suf + rightRes.suf);
    return res;
}

int main() {
    fin >> n >> t;
    for (int i = 1; i <= n; ++i)
        fin >> arr[i];
    createTree(1, n, 1);
    for (int i = 0; i < t; ++i) {
        int x, y;
        Node sol;
        fin >> x >> y;
        sol = findMax(x, y, 1, n, 1);
        fout << sol.sol << '\n';
    }
    return 0;
}