#include <fstream>
#include <cstdio>
#define Nmax 100001
using namespace std;


ofstream g("sequencequery.out");

int T=1,m,n,x,y;

struct ARB{
    int smaxS,smaxD,smax,stot;
}arb[Nmax*3+4];

void Up(int nod)
{
    arb[nod].smax = max(max(arb[nod*2].smax,arb[nod*2+1].smax),arb[nod*2].smaxD+arb[nod*2+1].smaxS);
    arb[nod].smaxD = max(arb[nod*2+1].stot+arb[nod*2].smaxD,arb[nod*2+1].smaxD);
    arb[nod].smaxS = max(arb[nod*2].stot+arb[nod*2+1].smaxS,arb[nod*2].smaxS);
    arb[nod].stot = arb[nod*2].stot+arb[nod*2+1].stot;
    if (nod!=1)
        Up(nod/2);
}

ARB query(int nod, int a, int b, int st, int dr)
{
    if(st<=a && b<=dr)
        return arb[nod];
    int mid = (a+b)/2;
    if (dr<=mid)
        return query(nod*2,a,mid,st,dr);
    else if (st>mid)
        return query(nod*2+1,mid+1,b,st,dr);
    else if (st<=mid && dr>=mid)
    {
        ARB A = query(nod*2,a,mid,st,dr);
        ARB B = query(nod*2+1,mid+1,b,st,dr);
        ARB aux;
        aux.smax = max(max(A.smax,B.smax),A.smaxD+B.smaxS);
        aux.smaxD = max(B.stot+A.smaxD,B.smaxD);
        aux.smaxS = max(A.stot+B.smaxS,A.smaxS);
        aux.stot = A.stot+B.stot;
        return aux;
    }

}


void Up2(int nod)
{
    if (nod*2<=T)
    {
        Up2(nod*2+1);
        Up2(nod*2);
    }
    arb[nod].smax = max(max(arb[nod*2].smax,arb[nod*2+1].smax),arb[nod*2].smaxD+arb[nod*2+1].smaxS);
    arb[nod].smaxD = max(arb[nod*2+1].stot+arb[nod*2].smaxD,arb[nod*2+1].smaxD);
    arb[nod].smaxS = max(arb[nod*2].stot+arb[nod*2+1].smaxS,arb[nod*2].smaxS);
    arb[nod].stot = arb[nod*2].stot+arb[nod*2+1].stot;
}


int main()
{
    freopen("sequencequery.in","r",stdin);

    scanf("%ld%ld",&n,&m);

    int sav=n;
    while (sav!=0)
    {
        sav/=2;
        T*=2;
    }

    T--;
    for (int i=1;i<=n;i++)
    {
        scanf("%ld",&x);
        arb[T+i].stot = x;
        arb[T+i].smaxD = x;
        arb[T+i].smaxS = x;
        arb[T+i].smax = x;
    }
    Up2(1);


    for (int i=1;i<=m;i++)
    {
        scanf("%ld%ld",&x,&y);
        g<<query(1,1,T+1,x,y).smax<<'\n';
    }


    return 0;
}