#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] = max(L[2*n], S[2*n] + L[2*n+1]);
    R[n] = max(R[2*n+1], S[2*n+1] + 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 = max(left.ml, left.sum + right.ml);
        ret.mr = max(right.mr, right.sum + 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;
}