#include <fstream>

using namespace std;

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

struct Aint
{
    long long s_max, prefix, sufix, suma;
};

Aint aint[800000];
int v[200005];

Aint Combine_Nod(Aint nod_1, Aint nod_2)
{
    Aint rez;
    rez.suma = nod_1.suma + nod_2.suma;
    rez.prefix = max(nod_1.prefix, nod_1.suma + nod_2.prefix);
    rez.sufix = max(nod_2.sufix, nod_2.suma + nod_1.sufix);
    rez.s_max = max(nod_1.s_max, nod_2.s_max);
    rez.s_max = max(rez.s_max, nod_1.sufix+nod_2.prefix);
    return rez;
}

void build(int nod, int left, int right)
{
    if(left == right)
    {
        aint[nod].s_max = v[left];
        aint[nod].suma = v[left];
        aint[nod].prefix = v[left];
        aint[nod].sufix = v[left];
        return;
    }
    int mid = (left + right) / 2;
    build(nod*2, left, mid);
    build(nod*2+1, mid + 1, right);
    aint[nod] = Combine_Nod(aint[nod*2], aint[nod*2+1]);
}

Aint query(int nod, int left, int right, int q_left, int q_right)
{
    if(q_left <= left && q_right >= right)
    {
        return aint[nod];
    }
    Aint rez;
    int mid = (left + right) / 2;
    bool stanga = 0;
    if(q_left <= mid)
    {
        rez = query(nod*2, left, mid, q_left, q_right);
        stanga = 1;
    }
    if(mid < q_right)
    {
        if(stanga == 1)
        {
            rez = Combine_Nod(rez, query(nod*2+1, mid+1, right, q_left, q_right));
        } else
        {
            rez = query(nod*2+1, mid+1, right, q_left, q_right);
        }
    }
    return rez;
}

int main()
{
    Aint rez;
    int n, m, i, a, b;
    in >> n >> m;
    for(i = 1; i <= n; i++)
    {
        in >> v[i];
    }
    build(1, 1, n);
    for(i = 1; i <= m; i++)
    {
        in >> a >> b;
        rez = query(1, 1, n, a, b);
        out << rez.s_max << '\n';
    }
    return 0;
}