#include <fstream>

using namespace std;

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

struct nod
{
    long long total, prefix, sufix, smax;
};

nod t[N];
bool completat[N];

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

long long max(long long a, long long b, long long c)
{
    return max(a, max(b, c));
}

nod combin(nod x, nod y)
{
    nod rez;
    rez.total = x.total + y.total;
    rez.prefix = max(x.prefix, x.total + y.prefix);
    rez.sufix = max(y.sufix, x.sufix + y.total);
    rez.smax = max(x.smax, y.smax, x.sufix + y.prefix);
    return rez;
}

void actualizare(int p, int st, int dr, int poz, int val)
{
    if (st == dr)
    {
        t[p].prefix = t[p].smax = t[p].sufix = t[p].total = val;
        completat[p] = true;
        return;
    }
    int m = (st + dr) / 2, fs = 2*p, fd = 2*p + 1;
    if (poz <= m)
    {
        actualizare(fs, st, m, poz, val);
    }
    else
    {
        actualizare(fd, m + 1, dr, poz, val);
    }
    if (completat[fs] && completat[fd])
    {
        t[p] = combin(t[fs], t[fd]);
    }
    else if (completat[fs])
    {
        t[p] = t[fs];
    }
    else
    {
        t[p] = t[fd];
    }
    completat[p] = true;
}

void scrie(int p, int st, int dr)
{
    out << p << ": [" << st << " , " << dr << "] : " << t[p].prefix << " " << t[p].sufix << " " << t[p].smax << "\n";
    if (st < dr)
    {
        int m = (st + dr) / 2;
        scrie(2*p, st, m);
        scrie(2*p + 1, m + 1, dr);
    }
}

nod interogare(int p, int st, int dr, int a, int b)
{
    if (a <= st && dr <= b)
    {
        return t[p];
    }
    int m = (st + dr) / 2, fs = 2*p, fd = 2*p + 1;
    if (a <= m && b > m)//[a,b] se intersecteaza cu ambii fii
    {
        nod q_st = interogare(fs, st, m, a, b);
        nod q_dr = interogare(fd, m+1, dr, a, b);
        return combin(q_st, q_dr);
    }
    if (a <= m)
    {
        return interogare(fs, st, m, a, b);
    }
    return interogare(fd, m+1, dr, a, b);
}

int main()
{
    int n, m;
    in >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        int aux;
        in >> aux;
        actualizare(1, 1, n, i, aux);
    }
    //scrie(1, 1, n);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        in >> a >> b;
        nod rez = interogare(1, 1, n, a, b);
        out << rez.smax << "\n";
    }
    in.close();
    out.close();
    return 0;
}