#include <bits/stdc++.h>

using namespace std;

#define nmax 400066
#define valmin -100000

int mx(int a, int b)
{
    return a>b?a:b;
}

struct nod
{
    long suma;
    int pref=valmin,suf=valmin,mid=valmin;
    void operator =(const int &b)
    {
        mid=b;
        pref=b;
        suf=b;
        suma=b;
    }
};

vector <nod> arbint(nmax);
int poz;
nod val;

int N,M;

vector<nod> qres;
int start,finish;

void update(int n, int left, int right)
{
    if(left==right)
    {
        arbint[n]=val;
        return;
    }
    int div=(left+right)/2;
    if(poz<div) update(n*2,left,div);
    else update(n*2+1,div+1,right);

    arbint[n].mid=mx(arbint[n*2].mid,mx(arbint[n*2+1].mid,arbint[n*2].suf+arbint[n*2+1].pref));
    arbint[n].pref=mx(arbint[n*2].pref,arbint[n*2].suma+arbint[n*2+1].pref);
    arbint[n].suf=mx(arbint[n*2+1].suf,arbint[n*2+1].suma+arbint[n*2].suf);
    arbint[n].suma=arbint[n*2].suma+arbint[n*2+1].suma;
}

void query(int n,int left,int right)
{
    if(start<=left&&right<=finish)
    {
        qres.push_back(arbint[n]);
        return;
    }
    int div=(left+right)/2;
    if(start<=div) query(n*2,left, div);
    if(div<finish) query(n*2+1,div+1,right);
}

int main()
{
    //freopen("sequencequery.in","r",stdin);
    //freopen("sequencequery.out","w",stdout);


    long maxim, sufmx;

    scanf("%i %i",&N,&M);
    for(int i=0;i<N;i++)
    {
        int nr;
        scanf("%i",&nr);
        val=nr, poz=i;
        update(1,1,N);
    }

    /*for(int i=0;i<N*4;i++)
    {
        cout<<arbint[i].mid<<' '<<arbint[i].pref<<' '<<arbint[i].suf<<' '<<arbint[i].suma<<'\n';
        for(int j=0;j<log(i);j++)
            cout<<"   ";
    }*/

    for(int i=0;i<M;i++)
    {
        maxim=valmin,sufmx=valmin;
        scanf("%i %i",&start,&finish);
        query(1,1,N);
        for(int j=0;j<qres.size();j++)
        {
            maxim=mx(maxim,mx(qres[j].mid,sufmx+qres[j].pref));

            if(j==0) sufmx=qres[j].suf;
            else sufmx=mx(sufmx+qres[j].suma,qres[j].suf);
        }
        qres.clear();
        printf("%i \n", maxim);
    }
    return 0;
}