/*Folosim Arbori de intervale
*/
#include<fstream>
#include<vector>
#include<string>
const int NMAX =  100000;

using namespace std;

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

struct arbore
{
    long long s, l , r, m;
    /*
    s-suma
    l-subsecventa maxim incepand din stanga
    dr-subsecventa maxim incepand din dreapta
    m-subsecventa maxima din mijloc

    */
}tree[400010];


string sir;
int i, n, k, j, m, nr, x , y;
long long int sol, aux;


void query(int nod, int stanga, int dreapta, int start, int finish)
{
    if(start <= stanga && dreapta <= finish)
    {
        sol = max(sol, max(tree[nod].m, aux + tree[nod].l ));
        aux = max(aux + tree[nod].s, tree[nod].r);

         //solution=max(solution,max(tree[node].m,dp+tree[node].l));
        //dp=max(dp+tree[node].s,tree[node].r);
        return;

        return;
    }
    int mij = (stanga + dreapta) / 2;
    if(start <= mij)
    {
        query(2 * nod, stanga, mij, start, finish);
    }
    if(mij < finish)
    {
        query(2 * nod + 1,  mij + 1, dreapta, start, finish);
    }
}


void update(int nod, int stanga, int dreapta, int position, int value, bool construieste)
{
    if(stanga == dreapta)
    {
        if(construieste == true)
        {
            tree[nod].s = value;//suma intregului interval
            tree[nod].l = value;//suma in stanga
            tree[nod].r = value;//suma in dreapta
            tree[nod].m = value;//suma in mijloc
        }
        else
        {
            //TODO

        }

        return;
    }
    int mij = (stanga + dreapta) / 2;
    if(position <= mij)
    {
        update(2 * nod, stanga, mij, position, value, construieste);
    }
    else
    {
        update(2 * nod + 1, mij + 1, dreapta, position, value, construieste);
    }
    tree[nod].s =  tree[2 * nod].s + tree[2 * nod + 1].s;
    tree[nod].l = max(tree[2 * nod].l, tree[2 * nod].s + tree[2 * nod + 1].l);
    tree[nod].r = max(tree[2 * nod + 1].r ,tree[2 * nod].r + tree[2 * nod + 1].s);
    tree[nod].m = max(max(tree[2 * nod].m, tree[2 * nod + 1].m),tree[2 * nod].r + tree[2 * nod + 1].l);
}

int main()
{
    fin >> n >> m;
    for(i = 1; i <= n; i++)
    {
        fin >> nr;
        update(1, 1, n, i, nr, true);
    }
    for(i = 1; i <= m; i++)
    {
        fin >> x >> y;
        sol = aux = -1000000000;
        query(1, 1, n, x, y);
        fout << sol << "\n";
    }
}