#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxN 200004
#define inf 2000000000
using namespace std;
int i, p, q, n, m, v[maxN], s[maxN], sb[maxN], se[maxN], S[maxN], smax, sum;
inline int left_son(int x)
{
    return 2 * x;
}
inline int right_son(int x)
{
    return 2 * x + 1;
}
void update(int node, int left, int right)
{
    int mid = (left + right) / 2;
    if (left == right)
    {
        S[node] = s[node] = sb[node] = se[node] = q;
        return;
    }
    if (p <= mid)
        update(left_son(node), left, mid);
    else
        update(right_son(node), mid + 1, right);

    S[node] = S[left_son(node)] + S[right_son(node)];
    sb[node] = max(sb[left_son(node)], S[left_son(node)] + sb[right_son(node)]);
    se[node] = max(se[right_son(node)], S[right_son(node)] + se[left_son(node)]);
    s[node] = max(s[left_son(node)], s[right_son(node)]);
    s[node] = max(s[node], se[left_son(node)] + sb[right_son(node)]);
}
void query(int node, int left, int right)
{
    int mid = (left + right) / 2;
    if (p <= left && q >= right)
    {
        smax = max(smax, max(s[node], sum + sb[node]));
        sum = max(sum + S[node], se[node]);
        return;
    }
    if (p <= mid)
        query(left_son(node), left, mid);
    if (q >= mid + 1)
        query(right_son(node), mid + 1, right);
}
void read()
{
    freopen("sequencequery.in", "r", stdin);
    scanf("%d %d", &n, &m);

    for (i = 1; i <= n; ++ i)
    {
        scanf("%d", &v[i]);
        p = i; q = v[i];
        update(1, 1, n);
    }
}
void write()
{
    freopen("sequencequery.out", "w", stdout);
    while (m --)
    {
        scanf("%d %d", &p, &q);
        smax = -inf;
        sum = 0;
        query(1, 1, n);
        printf("%d\n", smax);
    }
}
int main()
{
    read();
    write();
    return 0;
}