#include <iostream>
#include <stdio.h>
#include <fstream>

using namespace std;
typedef long long ll;
const int Nmax = (1 << 18) + 5;
ll INF = 1ll << 50;

int A[Nmax];
// Q - raspuns;         S - suma totala;
// L - prefix maxim;    R - suffix maxim;

ll maxleft, maxright, maxim, sum;
ll Q[Nmax], S[Nmax], L[Nmax], R[Nmax];

ll max (ll x, ll y) { return x > y ? x : y; }

void build(int n, int l, int r)
{
    if (l == r) {
        Q[n] = S[n] = L[n] = R[n] = A[l];
        return;
    }

    int mid = (l + r) / 2;
    build(2*n, l, mid);
    build(2*n+1, mid+1, r);
    S[n] = S[2*n] + S[2*n+1];
    L[n] = L[2*n];
    if (L[2*n] == S[2*n] && L[2*n+1] > 0) L[n] += L[2*n+1];
    R[n] = R[2*n+1];
    if (R[2*n+1] == S[2*n+1] && R[2*n] > 0) R[n] += R[2*n];
    Q[n] = max(Q[2*n], Q[2*n+1]);
    Q[n] = max(Q[n], R[2*n]+L[2*n+1]);
    return;
}

struct ans {
    ll mx, sum, ml, mr;
};

ans query(int n, int l, int r, int  a, int b)
{
    if (a <= l && r <= b) {
        ans ret {Q[n], S[n], L[n], R[n]};
        return ret;
    }

    int mid = (l + r) / 2;

    ans left  { -INF, -INF, -INF, -INF };
    ans right { -INF, -INF, -INF, -INF };
    ans ret;

    if (a <= mid && mid < b)
    {
        left = query(2*n, l, mid, a, b);
        right = query(2*n+1, mid+1, r, a, b);
        ret.sum = left.sum + right.sum;
        ret.ml = left.ml;
        ret.mr = right.mr;
        if (left.ml == left.sum) ret.ml += right.ml;
        if (right.mr == right.sum) ret.mr += left.mr;
        ret.mx = max(left.mx, right.mx);
        ret.mx = max(ret.mx, left.mr + right.ml);
    } else if (a <= mid)
            ret = query(2*n, l, mid, a, b);
      else if (mid < b)
            ret = query(2*n+1, mid+1, r, a, b);

    return ret;
}

int main()
{
    ifstream f ("sequencequery.in");
    ofstream g ("sequencequery.out");
    int N, M, a, b;

    f >> N >> M;
    for (int i = 1; i <= N; i++)
        f >> A[i];

    build(1, 1, N);

    while(M--)
    {
        f >> a >> b;
        ans ret = query(1, 1, N, a, b);
        g << ret.mx << '\n';
    }

    return 0;
}