#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;

long long s[400000],d[400000],a[400000],t[400000];
int v[100100],N,M,l,r;

struct values{long long S, D , A, T;} w;

void update(int st, int dr, int nod)
{
    if(st==dr)
    {
        a[nod]=v[st];
        s[nod]=v[st];
        d[nod]=v[st];
        t[nod]=v[st];
        return;
    }

    int mij=(st+dr)/2;

    update(st, mij, 2*nod);

    update(mij+1, dr, 2*nod + 1);

    t[nod]=t[2*nod]+t[2*nod+1];
    s[nod]=max(t[2*nod]+s[2*nod+1],s[2*nod]);
    d[nod]=max(d[2*nod]+t[2*nod+1],d[2*nod+1]);
    a[nod]=max(max(a[2*nod],a[2*nod+1]),d[2*nod]+s[2*nod+1]);
    return;
}

values query(int l, int r, int st, int dr, int nod)
{
    //cout<<l<<" "<<r<<"\n";
    int mij = (st+dr)/2;

    if(l==st && r==dr)
    {
        w.A=a[nod], w.S=s[nod], w.D=d[nod], w.T=t[nod];
    } else if(r<=mij) {
        w = query(l,r,st,mij,2*nod);
    } else if(l>mij) {
        w = query(l,r,mij+1,dr,2*nod+1);
    } else {
        w = query(l,mij,st,mij,2*nod);
        long long A1 = w.A, S1 = w.S, D1 = w.D, T1 = w.T;

        w = query(mij+1,r,mij+1,dr,2*nod+1);
        long long A2 = w.A, S2 = w.S, D2 = w.D, T2 = w.T;

        w.T = T1+T2;
        w.S = max(T1+S2,S1);
        w.D = max(D1+T2,D2);
        w.A = max(max(A1,A2),D1+S2);
    }

    return w;

}

int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;++i)
    {
        scanf("%d",&v[i]);
    }

    update(1,N,1);

    for(int i=1;i<=M;++i)
    {
        scanf("%d%d",&l,&r);
        w = query(l,r,1,N,1);
        printf("%lld\n",w.A);
    }
    return 0;
}