#include <fstream>

using namespace std;

const int NMAX = 100001;

struct nodarb
{
    long long sst, sdr, sum, ssm;
};

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

nodarb ai[4 * NMAX];
int x, y, v[NMAX];
long long sec, sol;

void build(int rad, int st, int dr)
{
    if(st == dr) ai[rad] = {v[st], v[st], v[st], v[st]};
    else
    {
        int mij = (st + dr) / 2;
        build(2 * rad, st, mij);
        build(2 * rad + 1, mij + 1, dr);
        ai[rad].sst = max(ai[2 * rad].sst, ai[2 * rad].sum + ai[2 * rad + 1].sst);
        ai[rad].sdr = max(ai[2 * rad + 1].sdr, ai[2 * rad + 1].sum + ai[2 * rad].sdr);
        ai[rad].sum = ai[rad * 2].sum + ai[rad * 2 + 1].sum;
        ai[rad].ssm = max(ai[2 * rad].ssm, max(ai[2 * rad + 1].ssm, ai[rad * 2].sdr + ai[2 * rad + 1].sst));
    }
}

void query(int rad, int st, int dr)
{
    if(x <= st && y >= dr)
    {
        if(sec < 0) sec = 0;
        sol = max(sol, max(sec + ai[rad].sst, ai[rad].ssm));
        sec = max(sec + ai[rad].sum, ai[rad].sdr);
    }
    else
    {
        int mij = (st + dr) / 2;
        if(x <= mij) query(2 * rad, st, mij);
        if(y > mij) query(2 * rad + 1, mij + 1, dr);
    }
}

int main()
{
    int n, m;
    fin >> n >> m;
    for(int i = 1; i <= n; ++i) fin >> v[i];
    build(1, 1, n);
    while(m--)
    {
        fin >> x >> y;
        sec = sol = 1LL << 63;
        query(1, 1, n);
        fout << sol << '\n';
    }
    return 0;
}