#include<fstream>
#define inf 2000000000
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
long long s[300],st[300],dr[300],smax[300];
int v[100001];
int n,m,a,b;
long long ans,sum;
void build(int nod, int x, int y)
{
    if(x==y)
    {
        s[nod]=st[nod]=dr[nod]=smax[nod]=v[x];
        return;
    }
    int mid=(x+y)/2;
    build(2*nod,x,mid);
    build(2*nod+1,mid+1,y);
    s[nod]=s[2*nod]+s[2*nod+1];///suma totala
    st[nod]=max(st[2*nod],s[2*nod]+st[2*nod+1]);///suma la stanga
    dr[nod]=max(dr[2*nod+1],s[2*nod+1]+dr[2*nod]);///suma la dreapta
    smax[nod]=max(smax[2*nod],smax[2*nod+1]);///suma maxima
    smax[nod]=max(smax[nod],st[2*nod+1]+dr[2*nod]);
}

void query(int nod, int x, int y)
{
    if(a<=x&&y<=b)
    {
        ans=max(ans,max(smax[nod],sum+st[nod]));
        sum=max(sum+s[nod],dr[nod]);///partea dreapta
        return;
    }
    int mid=(x+y)/2;
    if(a<=mid)
        query(2*nod,x,mid);
    if(b>mid)
        query(2*nod+1,mid+1,y);
}
int main()
{
    int i;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        fin>>v[i];
    build(1,1,n);
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        ans=-inf,sum=-inf;
        query(1,1,n);
        fout<<ans<<'\n';
    }
    return 0;
}