#include <iostream>
#include <fstream>
using namespace std;

ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

const int INF = 999999999,
          NMAX = 100002;

int N, M, lf, rg;
int v[NMAX];
long long s, sol;

struct arbore
{
    long long tot, l, r, ans;
};
arbore A[4 * NMAX];

void Update(int nod, int left, int right)
{
    if(left == right)
    {
        A[nod].l = A[nod].r = A[nod].ans = A[nod].tot = v[left];
        return;
    }
    int mij = (left + right) / 2;
    Update(nod * 2, left, mij);
    Update(nod * 2 + 1, mij + 1, right);

    A[nod].l = max(A[nod * 2].l, A[nod * 2].tot + A[nod * 2 + 1].l);
    A[nod].r = max(A[nod * 2 + 1].r, A[nod * 2 + 1].tot + A[nod * 2].r);
    A[nod].tot = A[nod * 2].tot + A[nod * 2 + 1].tot;
    A[nod].ans = max(A[nod * 2].ans, max(A[nod * 2 + 1].ans, A[nod * 2 + 1].l + A[nod * 2].r));
}

void Querry(int nod, int left, int right)
{
    if(lf <= left && rg >= right)
    {
        if(s < 0)
            s = 0;
        sol = max(sol, max(s + A[nod].l, A[nod].ans));
        s = max(s + A[nod].tot, A[nod].r);
        return;
    }
    int mij = (left + right) / 2;
    if(lf <= mij)
        Querry(2 * nod, left, mij);
    if(rg > mij)
        Querry(2 * nod + 1, mij + 1, right);
}

int main()
{
    f >> N >> M;
    for(int i = 1; i <= N; i++)
        f >> v[i];
    Update(1, 1, N);
    for(int i = 1; i <= M; i++)
    {
        f >> lf >> rg;
        s = sol = -INF;
        Querry(1, 1, N);
        g << sol << '\n';
    }
    return 0;
}