#include <fstream>

using namespace std;

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

int N, M;
long long Sum[4 * 100005]; // Sum[nod] - suma secventei descrise de nod
long long Left[4 * 100005]; //Left[nod] - suma maxima a subsecventei care porneste din capatul stang
long long Right[4 * 100005]; //Right[nod] - suma maxima a subsecventei care se termina in capatul drept
long long Best[4 * 100005]; //Best[nod] - suma maxima a subsecventei descrise de secventa specifica lui nod
long long temp_sum, ans; //temp_sum va denota suma maxima curenta a intervalului inainte de interogarea altui nod in arbore (sa se stie daca legam sau nu nodul curent)
                        //ans va reprezenta raspunsul per query


void Update(int nod, int st, int dr, int val, int poz)
{
    if (st == dr)
    {
        Sum[nod] = Left[nod] = Right[nod] = Best[nod] = val;
        return ;
    }
    int mid = (st + dr) >> 1;
    if (poz <= mid)
        Update(nod << 1, st, mid, val, poz);
    else
        Update((nod << 1) + 1, mid + 1, dr, val, poz);

    Sum[nod] = Sum[(nod << 1)] + Sum[(nod << 1) + 1];
    Left[nod] = max(Left[(nod << 1)], Sum[(nod << 1)] + Left[(nod << 1) + 1]);
    Right[nod] = max(Right[(nod << 1) + 1], Sum[(nod << 1) + 1] + Right[(nod << 1)]);
    Best[nod] = max(max(Best[(nod << 1)], Best[(nod << 1) + 1]), Left[(nod << 1) + 1] + Right[(nod << 1)]);
}

void Query(int nod, int st, int dr, int secv_st, int secv_dr)
{
    if (secv_st <= st && dr <= secv_dr)
    {
        ans = max(ans, max(temp_sum + Left[nod], Best[nod])); //vedem daca luam best[nod] sau legatura de dinainte de secv. nodului x + left
                                                            //apoi vedem daca e mai buna ca answer
        temp_sum = max(temp_sum + Sum[nod], Right[nod]); //tinem minte cea mai buna suma temporara pt viitor (doar din capatul drept sau o prelungim cu tot intervalul + ce era inainte)
        return ;
    }
    int mid = (st + dr) >> 1;
    if (secv_st <= mid)
        Query(nod << 1, st, mid, secv_st, secv_dr);
    if (secv_dr > mid)
       Query((nod << 1) + 1, mid + 1, dr, secv_st, secv_dr);
}

int main()
{
    f >> N >> M;
    for (int i = 1; i <= N; ++i)
    {
        int x;
        f >> x;
        Update(1, 1, N, x, i);
    }
    for (int i = 1; i <= M; ++i)
    {
        int a, b;
        f >> a >> b;
        temp_sum = 0;
        ans = -1000000000000000000;
        Query(1, 1, N, a, b);
        g << ans << "\n";
    }
    f.close();
    g.close();
    return 0;
}