#include <fstream>
#include<climits>
using namespace std;
ifstream cin ("sequencequery.in");
ofstream cout ("sequencequery.out");
int a[300100],b[300100],c[300100],d[300100],n,m,val,poz,e,f,maxim,sum,last;
void up_date (int st,int dr,int nod)
{
    if(st==poz && dr==poz) a[nod]=b[nod]=d[nod]=c[nod]=val;
    else
    {
        int mij=(st+dr)/2;
        if(poz<=mij) up_date(st,mij,nod*2);
        else up_date(mij+1,dr,nod*2+1);
        d[nod]=d[nod*2]+d[nod*2+1];
        a[nod]=max(a[nod*2],d[nod*2]+a[nod*2+1]);
        a[nod]=max(a[nod],d[nod]);
        b[nod]=max(b[nod*2+1],d[nod*2+1]+b[nod*2]);
        b[nod]=max(b[nod],d[nod]);
        c[nod]=max(c[nod*2],c[nod*2+1]);
        c[nod]=max(c[nod],a[nod]);
        c[nod]=max(c[nod],b[nod]);
        c[nod]=max(c[nod],b[nod*2]+a[nod*2+1]);
    }
}
void ask_me (int st,int dr,int nod)
{
    if(e<=st && dr<=f)
    {
        maxim=max(maxim,c[nod]);
        maxim=max(maxim,sum+a[nod]);
        sum=max(sum+d[nod],b[nod]);
    }
    else
    {
        int mij=(st+dr)/2;
        if(e<=mij) ask_me(st,mij,nod*2);
        if(f>mij) ask_me(mij+1,dr,nod*2+1);
    }
}
void read ()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>val; poz=i;
        up_date(1,n,1);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>e>>f; sum=0;
        maxim=-INT_MAX;
        ask_me(1,n,1);
        cout<<maxim<<"\n";
    }
}
int main()
{
    read();
    cin.close();
    cout.close();
    return 0;
}