#include <fstream>
#define MAXN 100005
#define INF 500000
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

struct nod_ai{
    long long a,b,c,d;};

int m,n,poz,el,mij,p,q,v[MAXN];
long long mx,S,mx2;
nod_ai ai[4*MAXN];
bool tip;

void query(int nod,int st,int dr);
void construieste_ai(int nod,int st,int dr);
long long MAX(long long x,long long y){
    return x>y?x:y;}

int main()
{
    int i;
    f>>n>>m;
    for(i=1;i<=n;i++)
        f>>v[i];
    construieste_ai(1,1,n);
    for(i=1;i<=m;i++){
        f>>p>>q;
        mx=-INF;
        S=0;
        query(1,1,n);
        g<<mx<<'\n';}
    f.close();
    g.close();
    return 0;
}

void query(int nod,int st,int dr){
    if(st>=p&&dr<=q){
        mx2=MAX(ai[nod].c,ai[nod].a+S);
        mx=MAX(mx,mx2);
        S=MAX(S+ai[nod].d,ai[nod].b);}
    else{
        mij=(st+dr)/2;
        if(mij>=p)
            query(2*nod,st,mij);
        mij=(st+dr)/2;
        if(q>mij)
            query(2*nod+1,mij+1,dr);}}

void construieste_ai(int nod,int st,int dr){
    if(st==dr){
        ai[nod].d=v[st];
        ai[nod].a=ai[nod].b=ai[nod].c=v[st];}
    else{
        construieste_ai(2*nod,st,(st+dr)/2);
        construieste_ai(2*nod+1,(st+dr)/2+1,dr);
        ai[nod].d=ai[2*nod].d+ai[2*nod+1].d;
        ai[nod].a=MAX(ai[2*nod].d+ai[2*nod+1].a,ai[2*nod].a);
        ai[nod].b=MAX(ai[2*nod+1].b,ai[2*nod].b+ai[2*nod+1].d);
        mx=MAX(ai[2*nod].c,ai[2*nod+1].c);
        ai[nod].c=MAX(mx,ai[2*nod].b+ai[2*nod+1].a);}}