#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int dim = 50005;

int n,m,a[dim],stanga[dim],dreapta[dim],suma[dim];

struct nod
{
    int val,st,dr,suma;
};

vector<nod> da;

nod arb[4*dim];

void Build(int nod,int st,int dr)
{
    if (st == dr)
    {
        int val = a[st];
        arb[nod].val = val;
        arb[nod].suma = val;
        arb[nod].st = arb[nod].dr = val;
        return ;
    }

    int mid = (st+dr)/2;
    Build(2*nod,st,mid);
    Build(2*nod+1,mid+1,dr);

    arb[nod].suma = arb[2*nod].suma + arb[2*nod+1].suma;

    arb[nod].st = arb[2*nod].st;
    arb[nod].st = max(arb[nod].st, arb[2*nod].suma + arb[2*nod+1].st);

    arb[nod].dr = arb[2*nod+1].dr;
    arb[nod].dr = max(arb[nod].dr, arb[2*nod+1].suma + arb[2*nod].dr);

    arb[nod].val = max(arb[2*nod].val, max(arb[2*nod+1].val, arb[2*nod].dr + arb[2*nod+1].st));
}

void Querry(int nod,int st,int dr,int a,int b)
{
    if (a <= st && dr <= b)
    {
        da.push_back(arb[nod]);
        return ;
    }
    int mid = (st+dr)/2;
    if (a <= mid)
    {
        Querry(2*nod,st,mid,a,b);
    }
    if (b > mid)
    {
        Querry(2*nod+1,mid+1,dr,a,b);
    }
}

int main()
{
    in >> n >> m;
    for (int i=1; i<=n; i++) in >> a[i];
    int idk = 0;
    for (int i=1; i<=n; i++)
    {
        if (idk < 0) idk = 0;
        idk += a[i];
        suma[i] = suma[i-1] + a[i];
        stanga[i] = max(stanga[i-1], idk);
    }
    idk = 0;

    for (int i=n; i>=1; i--)
    {
        if (idk < 0) idk = 0;
        idk += a[i];
        dreapta[i] = max(dreapta[i+1], idk);
    }
    Build(1,1,n);



    for (int i=1,a,b; i<=m; i++)
    {
        in >> a >> b;
        da.clear();
        Querry(1,1,n,a,b);
        for (int i=1; i<da.size(); i++)
        {
            nod fictiune;
            fictiune.suma = da[i].suma + da[i-1].suma;

            fictiune.st = da[i-1].st;
            fictiune.st = max(fictiune.st, da[i-1].suma + da[i].st);

            fictiune.dr = da[i].dr;
            fictiune.dr = max(fictiune.dr, da[i].suma + da[i-1].dr);

            fictiune.val = max(da[i-1].val, max(da[i].val, da[i-1].dr + da[i].st));

            da[i] = fictiune;
        }
        out << da[da.size() - 1].val << "\n";
    }
    return 0;
}