#include <fstream>
#define MAX 100005
#define ll long long
#define INF 1000000000000
using namespace std;
ifstream fi("sequencequery.in");
ofstream fo("sequencequery.out");

ll A[MAX*4],B[MAX*4],C[MAX*4],D[MAX*4];
int nr[MAX];
int n,q;
int poz,val,st,dr;
ll rez,s;

void build(int nod,int l,int r)
{
    if (l==r)
    {
        A[nod]=nr[l];
        B[nod]=nr[l];
        C[nod]=nr[l];
        D[nod]=nr[l];
        return;
    }
    int mij=(l+r)/2;
    build(2*nod,l,mij);
    build(2*nod+1,mij+1,r);

    A[nod]=max(A[2*nod],D[2*nod]+A[2*nod+1]);
    B[nod]=max(B[2*nod+1],B[2*nod]+D[2*nod+1]);
    C[nod]=max(max(C[2*nod],C[2*nod+1]),B[2*nod]+A[2*nod+1]);
    D[nod]=D[2*nod]+D[2*nod+1];
}

void arataBuild(int nod,int l,int r)
{
    fo<<l<<"..."<<r<<": "<<"inceput "<<A[nod]<<", sfarsit "<<B[nod];
    fo<<", oriunde "<<C[nod]<<", total "<<D[nod]<<"\n";
    if (l==r)
        return;
    int mij=(l+r)/2;
    arataBuild(2*nod,l,mij);
    arataBuild(2*nod+1,mij+1,r);
}

void update(int nod,int l,int r)
{
    if (l==r)
    {
        A[nod]=val;
        B[nod]=val;
        C[nod]=val;
        D[nod]=val;
        return;
    }
    int mij=(l+r)/2;
    if (poz<=mij)
        update(2*nod,l,mij);
    else
        update(2*nod+1,mij+1,r);

    A[nod]=max(A[2*nod],D[2*nod]+A[2*nod+1]);
    B[nod]=max(B[2*nod+1],B[2*nod]+D[2*nod+1]);
    C[nod]=max(max(C[2*nod],C[2*nod+1]),B[2*nod]+A[2*nod+1]);
    D[nod]=D[2*nod]+D[2*nod+1];
}

void query(int nod,int l,int r)
{
    if (st<=l && r<=dr)
    {
        rez=max(rez,max(C[nod],s+A[nod]));
        s=max(B[nod],s+D[nod]);
        return;
    }
    int mij=(l+r)/2;
    if (st<=mij)
        query(2*nod,l,mij);
    if (dr>mij)
        query(2*nod+1,mij+1,r);
}

int main()
{
    fi>>n>>q;
    for (int i=1; i<=n; i++)
        fi>>nr[i];
    build(1,1,n);

    //arataBuild(1,1,n);
    //return 0;

    while (q--)
    {
        int a,b;
        fi>>a>>b;
        st=a;
        dr=b;

        s=0,rez=-INF;
        query(1,1,n);
        fo<<rez<<"\n";
    }

    return 0;
}