#include <bits/stdc++.h>
#define Dim 100008
#define Min -10000000009
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
void Substring(int,int,int);
int N,M,V[Dim],a,b;
long long S[Dim],ras,lim,add;
bool ok,must;

struct hai
{
    long long sum_max,inceput,lungime;
}Tree[2*Dim];

void Substring(int vertex,int left,int right)
{
    int which=left,start,lg=0,lenght;
    long ans=Min,sum=0;
    for(int i=left;i<=right;i++)
    {
        if(sum<0)
        {
            sum=V[i];
            lg=1;
            which=i;
        }
        else
        {
            sum+=V[i];
           lg++;
        }
        if(sum>ans)
        {
            ans=sum;
            lenght=lg;
            start=which;
        }

    }
    Tree[vertex]={ans,start,lenght};

}

void INIT(int nod,int st,int dr)
{
    if(st==dr)
    {
        Tree[nod]={V[st],st,1};
        return;
    }
    Substring(nod,st,dr);
    int mij=(st+dr)/2;
    INIT(2*nod,st,mij);
    INIT(2*nod+1,mij+1,dr);
}

void Query(int nod,int st,int dr)
{
    if(st>=a&&dr<=b)
    {
        if(ok)
        {
            add+=Tree[nod].sum_max;
            lim=Tree[nod].lungime+Tree[nod].inceput-1;
            ok=0;
            must=1;
            if(add>ras) ras=add;
            if(add<0)
            {
                must=0;
                add=0;
            }

        }
        else
        {
            long long aux=0;
            if(must) aux=S[Tree[nod].inceput-1]-S[lim];
            lim=Tree[nod].inceput+Tree[nod].lungime-1;
            add+=aux+Tree[nod].sum_max;
            if(add>ras) ras=add;
            if(add<0)
            {
                add=0;
                must=0;
            }

        }
        return;
    }
    else
    {
        int mij=(st+dr)/2;
        if(a<=mij)
        Query(2*nod,st,mij);
        if(b>=mij+1)
        Query(2*nod+1,mij+1,dr);
    }
}

int main()
{
    f>>N>>M;
    for(int i=1;i<=N;i++)
    {
        f>>V[i];
        S[i]=S[i-1]+V[i];
    }
    INIT(1,1,N);
    for(int i=1;i<=M;i++)
    {
       f>>a>>b;
       ras=Min;
       add=0;
       ok=1;
       Query(1,1,N);
       g<<ras<<'\n';
    }
    return 0;
}