#include<bits/stdc++.h>

using namespace std;

int fast(string s,string t)

{

    int dp[100][100];

    cin>>s>>t;

    for(int i=0; i<s.size(); ++i)

        for(int j=0; j<t.size(); ++j)

        {

            if(s[i]==t[j])

                dp[i][j]=dp[i-1][j-1];

            else

                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

        }

    return dp[s.size()-1][t.size()-1];

    for(int i=1;; --i)

        cout<<s[i];

}

struct helper
{

    long long st,dr,mij;

    long long sum;

};

const int N=200005;

helper aint[4*N];

int v[N];

void mrge(int nod)
{

    helper fiust=aint[2*nod];

    helper fiudr=aint[2*nod+1];

    helper &x=aint[nod];



    x.st=max(fiust.st,fiust.sum+fiudr.st);

    x.dr=max(fiudr.dr,fiudr.sum+fiust.dr);

    x.sum=fiust.sum+fiudr.sum;

    x.mij=max(max(fiust.mij,fiudr.mij),fiust.dr+fiudr.st);

}

const long long INF=1LL<<40;

void build(int nod,int st,int dr)
{

    if(st>dr)

        return;

    if(st==dr)
    {

        aint[nod]= {v[st],v[st],v[st],v[st]};

        return;

    }

    int mid=(st+dr)/2;

    build(2*nod,st,mid);

    build(2*nod+1,mid+1,dr);

    mrge(nod);

}



void update(int nod,int st,int dr,int upoz,int val)
{

    if(st>dr || upoz<st || upoz>dr)
    {

        return;

    }

    if(st==dr)
    {

        aint[nod]= {val,val,val,val};

        return;

    }

    int mid=(st+dr)/2;

    update(2*nod,st,mid,upoz,val);

    update(2*nod+1,mid+1,dr,upoz,val);

    mrge(nod);

}

void query(int nod,int st,int dr,int qst,int qdr,helper &rasp)
{

    if(st>dr || qdr<st || qst>dr)
    {

        return;

    }

    if(qst<=st && dr<=qdr)
    {

        rasp.mij=max(max(rasp.mij,aint[nod].mij),rasp.dr+aint[nod].st);

        rasp.dr=max(aint[nod].dr,aint[nod].sum+rasp.dr);

        return;

    }

    int mid=(st+dr)/2;

    query(2*nod,st,mid,qst,qdr,rasp);

    query(2*nod+1,mid+1,dr,qst,qdr,rasp);

}

int main()

{

    FILE*fin,*fout;

    fin=fopen("sequencequery.in","r");

    fout=fopen("sequencequery.out","w");

    int n,q;

    fscanf(fin,"%d%d",&n,&q);

    for(int i=1; i<=n; i++)
    {

        fscanf(fin,"%d",&v[i]);

    }

    build(1,1,n);

    for(int i=1; i<=q; i++)
    {

        int a,b;

        fscanf(fin,"%d%d",&a,&b);

        helper rasp= {-INF,-INF,-INF,-INF};

        query(1,1,n,a,b,rasp);

        fprintf(fout,"%lld\n",rasp.mij);

    }

    return 0;

}