#include<bits/stdc++.h>

#include <fstream>

#include <algorithm>

#include <cstdio>

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;



}