#include <fstream>
#include <cstdio>
#define N 100010
#define ARB pair<pair<long long,long long>,long long>
#define SQ second
#define SMax first.first
#define SMin first.second
#define INF 999999999999

using namespace std;

FILE* fin=fopen("sequencequery.in","r");
FILE* fout=fopen("sequencequery.out","w");
const int maxb=8192;
char buf[maxb];
int ptr=0;

inline long long getint()
{
    long long nr=0,s=1;
    while((buf[ptr]<'0'||'9'<buf[ptr])&&buf[ptr]!='-')
        if (++ptr>=maxb) fread(buf,maxb,1,fin),ptr=0;
    if (buf[ptr]=='-')
    {
        s=-1;
        if (++ptr>=maxb) fread(buf,maxb,1,fin),ptr=0;
        while((buf[ptr]<'0'||'9'<buf[ptr])&&buf[ptr]!='-')
            if (++ptr>=maxb) fread(buf,maxb,1,fin),ptr=0;
    }
    while ('0'<=buf[ptr]&&buf[ptr]<='9')
    {
        nr=nr*10+buf[ptr]-'0';
        if (++ptr>=maxb) fread(buf,maxb,1,fin),ptr=0;
    }
    return nr*s;
}

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

void Init ()
{
    for (int i = 0; i < 4*N; 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);
        ANS=max(ANS,AI[nod].SMax-P);
        P=min(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 (i=1;i<=n;i++)
    {
        x=getint();
        S[i]=S[i-1]+x*1LL;
    }

    Build(1,1,n);

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

    fclose(fin);fclose(fout);
    return 0;
}