#include <iostream>
#include <fstream>
#define nmax 100002
#define inf 10000000001
using namespace std;
struct arbore_intervale{
    long long ssm,smin,smax;
};
arbore_intervale aint[4*nmax];
long long n,m,v[nmax],dp[nmax];
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
inline long long maxim(long long a,long long b)
{
    if(a>b)
        return a;
    else return b;
}
inline long long minim(long long a,long long b)
{
    if(a<b)
        return a;
    else return b;
}
void build_aint(int nod,int st,int dr)
{
    if(st>dr)
        return;
    if(st==dr)
    {
        aint[nod].ssm=v[st];
        aint[nod].smin=dp[st-1];
        aint[nod].smax=dp[dr];
        return;
    }
    int mid=(st+dr)>>1;
    build_aint(2*nod,st,mid);
    build_aint(2*nod+1,mid+1,dr);
    aint[nod].smax=maxim(aint[2*nod].smax,aint[2*nod+1].smax);
    aint[nod].smin=minim(aint[2*nod].smin,aint[2*nod+1].smin);
    aint[nod].ssm=maxim(maxim(aint[2*nod].ssm,aint[2*nod+1].ssm),aint[2*nod+1].smax-aint[2*nod].smin);
}
void query(int nod,int st,int dr,int a,int b,long long&ssm,long long&prefmin)
{
    if(st>dr)
        return;
    if(st>b||dr<a)
        return;
    if(a<=st&&dr<=b)
    {
        long long curr=aint[nod].ssm;
        if(prefmin!=inf)
        {
            if(aint[nod].smax-prefmin>curr)
                   curr=aint[nod].smax-prefmin;
        }
        if(aint[nod].smin<prefmin)
            prefmin=aint[nod].smin;
        if(curr>ssm)
            ssm=curr;
        return;
    }
    int mid=(st+dr)>>1;
    query(2*nod,st,mid,a,b,ssm,prefmin);
    query(2*nod+1,mid+1,dr,a,b,ssm,prefmin);
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
        f>>v[i];
        dp[i]=v[i]+dp[i-1];
    }
    build_aint(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        f>>x>>y;
        long long ssm=-inf,prefmin=inf;
        query(1,1,n,x,y,ssm,prefmin);
        g<<ssm<<"\n";
    }
    return 0;
}