#include <fstream>
using namespace std;

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

struct Nod {
    long long suma_totala;
    long long suma_prefix;
    long long suma_sufix;
    long long suma_maxima;
} Arbore[400001];

Nod NodSumaMaxima (Nod stanga , Nod dreapta)
{
    Nod nod_actual;
    nod_actual.suma_totala = stanga.suma_totala + dreapta.suma_totala;
    nod_actual.suma_prefix = max(stanga.suma_prefix , stanga.suma_totala + dreapta.suma_prefix);
    nod_actual.suma_sufix = max(dreapta.suma_sufix , stanga.suma_sufix + dreapta.suma_totala);
    nod_actual.suma_maxima = max(stanga.suma_sufix + dreapta.suma_prefix , max(stanga.suma_maxima , dreapta.suma_maxima));
    return nod_actual;
}

void Build (int nod , int stanga , int dreapta)
{
    if (stanga == dreapta)
    {
        cin >> Arbore[nod].suma_totala;
        Arbore[nod].suma_sufix = Arbore[nod].suma_totala;
        Arbore[nod].suma_prefix = Arbore[nod].suma_totala;
        Arbore[nod].suma_maxima = Arbore[nod].suma_totala;
    }
    else
    {
        int mijloc = (stanga + dreapta) >> 1;

        Build((nod << 1) , stanga , mijloc);
        Build((nod << 1) + 1 , mijloc + 1 , dreapta);

        Arbore[nod] = NodSumaMaxima(Arbore[nod << 1] , Arbore[(nod << 1) + 1]);
    }
}

Nod SumaMaxima (int nod , int stanga , int dreapta , int stanga_interval , int dreapta_interval)
{
    if (stanga_interval <= stanga && dreapta <= dreapta_interval)
        return Arbore[nod];
    else
    {
        int mijloc = (stanga + dreapta) >> 1;

        if (dreapta_interval <= mijloc)
            return SumaMaxima((nod << 1) , stanga , mijloc , stanga_interval , dreapta_interval);

        if (stanga_interval > mijloc)
            return SumaMaxima((nod << 1) + 1 , mijloc + 1 , dreapta , stanga_interval , dreapta_interval);

        Nod nod_stanga = SumaMaxima((nod << 1) , stanga , mijloc , stanga_interval , dreapta_interval);
        Nod nod_dreapta = SumaMaxima((nod << 1) + 1 , mijloc + 1 , dreapta , stanga_interval , dreapta_interval);
        return NodSumaMaxima(nod_stanga , nod_dreapta);
    }
}

int main ()
{
    int lungime , intrebari;
    cin >> lungime >> intrebari;
    Build(1 , 1 , lungime);

    for (int indice = 1 , stanga , dreapta ; indice <= intrebari ; indice++)
        cin >> stanga >> dreapta , cout << SumaMaxima(1 , 1 , lungime , stanga , dreapta).suma_maxima << '\n';

    cout.close(); cin.close();
    return 0;
}