#include <bits/stdc++.h>
#pragma GCC optimize("O3,Ofast,unroll-loops")
using namespace std;

const int NMAX = 1000001;
int n, m;

struct Nod
{
    long long sum, pref, suf, best;
};

Nod aint[4 * NMAX];

Nod aduna(Nod a, Nod b)
{
    Nod rez;
    rez.sum = a.sum + b.sum;
    rez.pref = max(a.pref, a.sum + b.pref);
    rez.suf = max(b.suf, b.sum + a.suf);
    rez.best = max({a.best, b.best, a.suf + b.pref});
    return rez;
}

void update_recursiv(int nod, int stanga, int dreapta, int poz, long long val)
{
    if (stanga == dreapta)
    {
        aint[nod].sum = val;
        aint[nod].pref = max(LLONG_MIN, val);
        aint[nod].suf = max(LLONG_MIN, val);
        aint[nod].best = max(LLONG_MIN, val);
        return;
    }
    int mij = (stanga + dreapta) / 2;
    if (poz <= mij)
        update_recursiv(2 * nod, stanga, mij, poz, val);
    else
        update_recursiv(2 * nod + 1, mij + 1, dreapta, poz, val);
    aint[nod] = aduna(aint[2 * nod], aint[2 * nod + 1]);
}

void update(int poz, int val)
{
    update_recursiv(1, 1, n, poz, val);
}

Nod query_recursiv(int nod, int stanga, int dreapta, int query_x, int query_y)
{
    if (query_x > query_y)
    {
        Nod gol;
        gol.sum = 0;
        gol.pref = gol.suf = gol.best = 0;
        return gol;
    }

    if (stanga == query_x && dreapta == query_y)
        return aint[nod];

    int mij = (stanga + dreapta) / 2;
    if (query_y <= mij)
        return query_recursiv(2 * nod, stanga, mij, query_x, query_y);
    if (query_x > mij)
        return query_recursiv(2 * nod + 1, mij + 1, dreapta, query_x, query_y);

    Nod st = query_recursiv(2 * nod, stanga, mij, query_x, mij);
    Nod dr = query_recursiv(2 * nod + 1, mij + 1, dreapta, mij + 1, query_y);
    return aduna(st, dr);
}

int query(int query_x, int query_y)
{
    return query_recursiv(1, 1, n, query_x, query_y).best;
}

int main()
{
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        long long x;
        scanf("%d", &x);
        update(i, x);
    }

    for (int i = 1; i <= m; i++)
    {
        int st, dr;
        scanf("%d %d", &st, &dr);
        printf("%d\n", query(st, dr));
    }

    return 0;
}