#include <cstdio>
#include <cstdlib>
#include <ctype.h>
#define INF 2000000000000000
using namespace std;
long long t1[300000],t2[300000],t3[300000],t4[300000],v[300000];
struct gogu
{
    long long nr1,nr2,nr3,nr4;
};
long long max(long long a,long long b)
{
    if(a>b)
        return a;
    return b;
}
long long getINT()
{
    long long semn=1,nr=0;
    char c;
    c=getchar();
    while(c!='-' && isdigit(c)==0) c=getchar();
    if(c=='-')
    {
        semn=-1;
        c=getchar();
    }
    while(isdigit(c))
    {
        nr=nr*10+(c-'0');
        c=getchar();
    }
    return nr*semn;
}
void begin(long long st,long long dr,long long x,long long k,long long pos)
{
    if(st<dr)
    {
        if(k<=(st+dr)/2) begin(st,(st+dr)/2,x,k,pos*2);
        if(k>(st+dr)/2)  begin((st+dr)/2+1,dr,x,k,pos*2+1);
    }
    else
    {
        t1[pos]=t2[pos]=t3[pos]=t4[pos]=x;
        v[pos]=1;
    }
}
void update(long long pos)
{
    if(v[pos*2]!=1) update(pos*2);
    if(v[pos*2+1]!=1) update(pos*2+1);
    t1[pos]=t1[pos*2]+t1[pos*2+1];
    t2[pos]=max(t2[pos*2+1],t1[pos*2+1]+t2[pos*2]);
    t3[pos]=max(t3[pos*2],t1[pos*2]+t3[pos*2+1]);
    t4[pos]=max(t4[pos*2],t4[pos*2+1]);
    t4[pos]=max(t4[pos],t2[pos*2]+t3[pos*2+1]);
}
gogu functie(long long st,long long dr,long long a,long long b,long long pos)
{
    gogu x,y,k;
    x.nr2=y.nr2=x.nr3=y.nr3=x.nr4=y.nr4=-INF;
    x.nr1=y.nr1=0;
    k.nr1=t1[pos];
    k.nr2=t2[pos];
    k.nr3=t3[pos];
    k.nr4=t4[pos];
    if(a<=st && b>=dr)
        return k;
    else
    {
        if(a<=(st+dr)/2)
            x=functie(st,(st+dr)/2,a,b,pos*2);
        if(b>(st+dr)/2)
            y=functie((st+dr)/2+1,dr,a,b,pos*2+1);
        k.nr1=x.nr1+y.nr1;
        k.nr2=max(x.nr2,y.nr2);
        k.nr3=max(x.nr3,x.nr3);
        k.nr4=max(x.nr4,y.nr4);
        k.nr4=max(k.nr4,x.nr2+y.nr3);
        return k;

    }
}
int main()
{
    long long i,n,q,x,a,b;
    gogu k,kk;
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    n=getINT();
    q=getINT();
    for(i=1; i<=n; i++)
    {
        x=getINT();
        begin(1,n,x,i,1);
    }
    update(1);
    //for(i=1; i<=15; i++)
        //printf("%lld %lld %lld %lld\n",t1[i],t2[i],t3[i],t4[i]);
    for(i=1; i<=q; i++)
    {
        scanf("%lld%lld",&a,&b);
        k=functie(1,n,a,b,1);
        printf("%lld\n",k.nr4);
    }

    return 0;
}