#include <bits/stdc++.h>

using namespace std;

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

void usain_bolt()
{
    ios::sync_with_stdio(false);
    fin.tie(0);
}

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 = tree[node * 2].pref;
    if (tree[node * 2].pref == tree[node * 2].sum)
        tree[node].pref += max(0LL, tree[node * 2 + 1].pref);
    tree[node].suf = tree[node * 2 + 1].suf;
    if (tree[node * 2 + 1].suf == tree[node * 2 + 1].sum)
        tree[node].suf += max(0LL, 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].pref);
    tree[node].ssm = max(tree[node].ssm, tree[node].suf);
    tree[node].ssm = max(tree[node].ssm, max(0LL, tree[node * 2].suf) + max(0LL, tree[node * 2 + 1].pref));
    tree[node].ssm = max(tree[node].ssm, tree[node * 2].suf);
    tree[node].ssm = max(tree[node].ssm, 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 += tree[node].sum;
        last = max(0LL, 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()
{
    usain_bolt();

    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;
}