#include <iostream>
#include<fstream>
#include<climits>
//#ruleyourself
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
struct node
{
    long long sum,mx,st,dr;
}arb[400005];
long long maxim,x;
int start,fin,n,m,i,j,v[30],k,suma,relsum;
void update(int nod,int l,int r)
{
    if(l==r)
    {
        arb[nod].sum=x;
        arb[nod].mx=x;
        arb[nod].st=x;
        arb[nod].dr=x;
        return;
    }
    int m=(l+r)/2;
    if(i<=m) update(2*nod,l,m);
    else update(2*nod+1,m+1,r);
    arb[nod].sum=arb[2*nod].sum+arb[2*nod+1].sum;
    arb[nod].mx=max(arb[2*nod].dr+arb[2*nod+1].st,max(arb[2*nod].mx,arb[2*nod+1].mx));
    arb[nod].st=max(arb[2*nod].st,arb[2*nod].sum+arb[2*nod+1].st);
    arb[nod].dr=max(arb[2*nod+1].dr,arb[2*nod+1].sum+arb[2*nod].dr);
}
void query(int nod,int l,int r)
{
    if(start<=l&&r<=fin)
    {
        x++;
        v[x]=nod;
        return;
    }
    int m=(l+r)/2;
    if(start<=m) query(2*nod,l,m);
    if(m<fin) query(2*nod+1,m+1,r);
}
void returnmax()
{
    maxim=-LLONG_MAX;v[x+1]=0;
    for(j=1;j<=x;j++)
    {
        if(arb[v[j]].mx>maxim) maxim=arb[v[j]].mx;
    }
    for(j=1;j<=x;j++)
    {
        suma=0;
        if(arb[v[j]].dr+arb[v[j+1]].st>maxim) maxim=arb[v[j]].dr+arb[v[j+1]].st;
        for(k=j;k<=x;k++)
        {
            suma+=arb[v[k]].sum;
            relsum=suma;
            if(arb[v[j-1]].dr>0) relsum+=arb[v[j-1]].dr;
            if(arb[v[k+1]].st>0) relsum+=arb[v[k+1]].st;
            if(relsum>maxim) maxim=relsum;
        }
    }
    g<<maxim<<'\n';
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        f>>x;
        update(1,1,n);
    }
    for(i=1;i<=m;i++)
    {
        f>>start>>fin;
        x=0;
        query(1,1,n);
        returnmax();
    }
    return 0;
}