#include <fstream>

using namespace std;

const int N = 1 << 18;
const long long INF = 1LL << 60;

struct secv
{
    long long prefix, sufix, ssm, total;
};

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

secv aint[N];

void combin(secv &rez, secv &x, secv &y)
{
    rez.total = x.total + y.total;
    rez.prefix = x.prefix;
    rez.prefix = max(rez.prefix, x.total + y.prefix);
    rez.sufix = y.sufix;
    rez.sufix = max(rez.sufix, x.sufix + y.total);
    rez.ssm = max(x.ssm, y.ssm);
    rez.ssm = max(rez.ssm, x.sufix + y.prefix);
}

void constructie(int p, int st, int dr)
{
    if (st == dr)
    {
        in >> aint[p].total;
        aint[p].prefix = aint[p].sufix = aint[p].ssm = aint[p].total;
        return;
    }
    int m = (st + dr) / 2, fs = 2 * p, fd = 2 * p + 1;
    constructie(fs, st, m);
    constructie(fd, m + 1, dr);
    combin(aint[p], aint[fs], aint[fd]);
}

void interogare(int p, int st, int dr, int a, int b, secv &rez)
{
    if (a <= st && dr <= b)
    {
        rez = aint[p];
        return;
    }
    int m = (st + dr) / 2, fs = 2 * p, fd = 2 * p + 1;
    secv rez_st, rez_dr;
    rez_st = rez_dr = (secv){-INF, -INF, -INF, 0};
    if (a <= m)
    {
        interogare(fs, st, m, a, b, rez_st);
    }
    if (m + 1 <= b)
    {
        interogare(fd, m + 1, dr, a, b, rez_dr);
    }
    combin(rez, rez_st, rez_dr);
}

int main()
{
    int n, nq;
    in >> n >> nq;
    constructie(1, 1, n);
    for (int i = 0; i < nq; i++)
    {
        int a, b;
        secv rez;
        in >> a >> b;
        interogare(1, 1, n, a, b, rez);
        out << rez.ssm << "\n";
    }
    in.close();
    out.close();
    return 0;
}