#include <bits/stdc++.h>

#define NMAX ((int)1e5 + 5)
#define INF ((int)2e9)

using namespace std;

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

struct seg_info {
    long long best, left, right, sum;
};

long long n, m, x, y;
seg_info seg_tree[4 * NMAX + 5], sol;
long long arr[NMAX];

void build_seg_tree(long long node, long long left, long long right) {
    if (left == right) {
        seg_tree[node].best = arr[left];
        seg_tree[node].left = arr[left];
        seg_tree[node].right = arr[left];
        seg_tree[node].sum = arr[left];
    }
    else
    {
        long long mid = left + ((right - left) >> 1);
        build_seg_tree(2 * node, left, mid);
        build_seg_tree(2 * node + 1, mid + 1, right);

        seg_tree[node].best = max({
            seg_tree[2 * node].best,
            seg_tree[2 * node + 1].best,
            seg_tree[2 * node].right + seg_tree[2 * node + 1].left
        });

        seg_tree[node].sum = seg_tree[2 * node].sum + seg_tree[2 * node + 1].sum;
        seg_tree[node].left = max(seg_tree[2 * node].left, seg_tree[2 * node].sum + seg_tree[2 * node + 1].left);
        seg_tree[node].right = max(seg_tree[2 * node + 1].right, seg_tree[2 * node + 1].sum + seg_tree[2 * node].right);
    }
}
 
void query(long long node, long long seg_left, long long seg_right, long long query_left, long long query_right) {
    if (query_left <= seg_left && seg_right <= query_right) {
        if (sol.sum == -INF) {
            sol = seg_tree[node];
        } else {
            sol.best = max(sol.best, max(seg_tree[node].best, sol.right + seg_tree[node].left));
            sol.right = max(seg_tree[node].right, seg_tree[node].sum + sol.right);
        }
    } else {
        long long mid = seg_left + ((seg_right - seg_left) >> 1);
        if (query_left <= mid) {
            query(2 * node, seg_left, mid, query_left, query_right);
        }

        if (query_right > mid) {
            query(2 * node + 1, mid + 1, seg_right, query_left, query_right);
        }
    }
}

int main() {
    fin >> n >> m;
    for (long long i = 1; i <= n; ++i) {
        fin >> arr[i];
    }

    build_seg_tree(1, 1, n);

    for (long long i = 1; i <= m; ++i) {
        fin >> x >> y;
        sol.sum = -INF;

        query(1, 1, n, x, y);
        fout << sol.best << "\n";
    }

    return 0;
}