#include <fstream>
#include <cstdio>

using namespace std;

const int Nmax = 100010;

typedef long long I64; 

#define ARB pair<pair<I64,I64>,I64>

#define SQ second
#define SMax first.first
#define SMin first.second

#define INF 1LL<<60

using namespace std;

FILE* F=fopen("sequencequery.in","r");
FILE* G=fopen("sequencequery.out","w");

const int BufferferS=8192;
char Buffer[BufferferS];
int Act=0;

inline I64 getint()
{
    I64 nr=0,s=1;
    while((Buffer[Act]<'0'||'9'<Buffer[Act])&&Buffer[Act]!='-')
        if (++Act>=BufferferS) fread(Buffer,BufferferS,1,F),Act=0;
    if (Buffer[Act]=='-')
    {
        s=-1;
        if (++Act>=BufferferS) fread(Buffer,BufferferS,1,F),Act=0;
        while((Buffer[Act]<'0'||'9'<Buffer[Act])&&Buffer[Act]!='-')
            if (++Act>=BufferferS) fread(Buffer,BufferferS,1,F),Act=0;
    }
    while ('0'<=Buffer[Act]&&Buffer[Act]<='9')
    {
        nr=nr*10+Buffer[Act]-'0';
        if (++Act>=BufferferS) fread(Buffer,BufferferS,1,F),Act=0;
    }
    return nr*s;
}

I64 S[Nmax],ANS,P;
int i,n,x,y,st,dr,m;
ARB AI[4*Nmax];

void Init ()
{
    for (int i = 0; i < 4*Nmax; i++)
    {
        AI[i].SQ = AI[i].SMax = -INF;
        AI[i].SMin = INF;
    }
}

void Build (int nod, int l, int r)
{
    if (l>=r)
    {
        AI[nod].SQ=S[r]-S[r-1];
        AI[nod].SMax=S[r];
        AI[nod].SMin=S[r-1];
        return;
    }
    int m=(l+r)/2;
    Build(2*nod,l,m);
    Build(2*nod+1,m+1,r);
    AI[nod].SQ=max(AI[2*nod+1].SMax-AI[2*nod].SMin,max(AI[2*nod].SQ,AI[2*nod+1].SQ));
    AI[nod].SMin=min(AI[2*nod].SMin,AI[2*nod+1].SMin);
    AI[nod].SMax=max(AI[2*nod].SMax,AI[2*nod+1].SMax);
}

void Query (int nod, int l, int r)
{
    if (l>=st && r<=dr)
    {
        ANS=max(ANS,AI[nod].SQ);
        if (P<INF)
        {
            ANS=max(ANS,AI[nod].SMax-P);
            P=min(P,AI[nod].SMin);
        }
        else P=AI[nod].SMin;
        return;
    }
    int m=(l+r)/2;
    if (st<=m) Query(2*nod,l,m);
    if (dr>m) Query(2*nod+1,m+1,r);
}

int main ()
{
    Init();
    n=getint();m=getint();
    for (int i=1;i<=n;i++)
    {
        x=getint();
        S[i]=S[i-1]+x*1LL;
    }

    Build(1,1,n);

    for (int i=1;i<=m;i++)
    {
        st=getint();dr=getint();
        ANS=-INF;P=INF;
        Query(1,1,n);
        fprintf(G,"%lld\n",ANS);
    }
}