#include <bits/stdc++.h>
using namespace std;
ifstream fin ("sequencequery.in");
ofstream fout ("sequencequery.out");
const int N = 1e5 + 5;
int a[N];
long long ans, last;
struct solve
{
    long long pref, suf, ssm, sum;
} tree[N * 4];
void build(int left, int right, int node)
{
    if (left > right)
        return;
    if (left == right) {
        tree[node].pref = 1LL * a[left];
        tree[node].suf = 1LL * a[left];
        tree[node].ssm = 1LL * a[left];
        tree[node].sum = 1LL * a[left];
        return;
    }
    int mid = (left + right) >> 1;
    build(left, mid, node * 2);
    build(mid + 1, right, node * 2 + 1);
    tree[node].sum = tree[node * 2].sum + tree[node * 2 + 1].sum;
    tree[node].pref = max(tree[node * 2].pref, tree[node * 2].sum + tree[node * 2 + 1].pref);
    tree[node].suf = max(tree[node * 2 + 1].suf, tree[node * 2 + 1].sum + tree[node * 2].suf);
    tree[node].ssm = max(tree[node * 2].ssm, tree[node * 2 + 1].ssm);
    tree[node].ssm = max(tree[node].ssm, tree[node * 2].suf + tree[node * 2 + 1].pref);
}
void query(int left, int right, int node, int x, int y)
{
    if (left >= x && right <= y) {
        ans = max(ans, tree[node].ssm);
        ans = max(ans, tree[node].pref + last);
        last = max(last + tree[node].sum, tree[node].suf);
        ans = max(ans, last);
        return;
    }
    int mid = (left + right) >> 1;
    if (mid >= x)
        query(left, mid, node * 2, x, y);
    if (mid + 1 <= y)
        query(mid + 1, right, node * 2 + 1, x, y);
}
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
    int n, q;
    fin >> n >> q;
    for (int i = 1; i <= n; ++i)
        fin >> a[i];
    build(1, n, 1);
    for(; q; --q) {
        int x, y;
        fin >> x >> y;
        ans = -2e18, last = 0LL;
        query(1, n, 1, x, y);
        fout << ans << "\n";
    }
    return 0;
}