#include <iostream>
#include <fstream>
#include <algorithm>


using namespace std;

int n, m, v[100010], A, B, INF = 2000000000;
long long rez, suma;
struct arbore
{
    long long L, R, best, sum;
};
arbore aint[262145];

inline void Build (int nod, int st, int dr)
{
    if (st == dr)
    {
        aint[nod].L = aint[nod].R = aint[nod].best = aint[nod].sum = v[st];
        return ;
    }
    int mij = (st+dr)>>1, fiu = nod<<1;
    Build (fiu, st, mij);
    Build (fiu+1, mij+1, dr);
    aint[nod].L = max(aint[fiu].L, aint[fiu].sum + aint[fiu+1].L);
    aint[nod].R = max(aint[fiu+1].R, aint[fiu+1].sum + aint[fiu].R);
    aint[nod].best = max(max(aint[fiu].best, aint[fiu+1].best), aint[fiu].R + aint[fiu+1].L);
    aint[nod].sum = aint[fiu].sum + aint[fiu+1].sum;
}

inline void Query(int nod, int st, int dr)
{
    if (A <= st && dr <= B)
    {
        if (suma < 0)
            suma = 0;
        rez = max(rez, max(aint[nod].best, aint[nod].L+suma));
        suma = max(aint[nod].R, aint[nod].R + suma);
        return ;
    }
    int mij = (st+dr)>>1, fiu = nod<<1;
    if (A <= mij)
        Query (fiu, st, mij);
    if (mij < B)
        Query (fiu+1, mij+1, dr);
}

inline void Solve ()
{
    ifstream f ("sequencequery.in");
    ofstream g ("sequencequery.out");
    f>>n>>m;
    int i, x, y;
    for (i=1; i<=n; i++)
        f>>v[i];
    Build(1, 1, n);
    while (m)
    {
        m--;
        f>>x>>y;
        A = x;
        B = y;
        suma = 0;
        rez = -INF;
        Query(1, 1, n);
        g<<rez<<"\n";
    }
    f.close();
    g.close();
}

int main()
{
    Solve();
    return 0;
}