#include <iostream>
#include <fstream>
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
string s;
long long arbl[400005],arbr[400005],n,m,vl[100005],vr[100005],x,y,ch;
long long bestsum, inf=(1LL<<62),pre,suf,a,b;

int nextint()
{
    int num=0;
    bool ok=true;
    while(s[ch]==' ') ++ch;
    if(s[ch]=='-')
    {
        ok=false;
        ++ch;
    }
    while(s[ch]>='0' && s[ch]<='9')
    {
        num=num*10+s[ch]-'0';
        ++ch;
    }
    if(!ok) num=-num;
    return num;
}

void build(int nod,int lt,int rt,int pos,int op)
{
    if(lt==rt)
    {
       if(op) arbl[nod]=vl[pos];
       else arbr[nod]=vr[pos];
        return;
    }
    int md=(lt+rt)/2;
    if(pos<=md) build(nod*2,lt,md,pos,op);
    else build(nod*2+1,md+1,rt,pos,op);

    if(op)arbl[nod]=max(arbl[nod*2],arbl[nod*2+1]);
    else arbr[nod]=max(arbr[nod*2],arbr[nod*2+1]);
}

void query(int nod,int lt,int rt,int q,int w,int op)
{
    if(q<=lt && rt<=w)
    {
        if(op) suf=max(suf,arbl[nod]);
        else pre=max(pre,arbr[nod]);
        return;
    }
    if(lt==rt) return;
    int md=(lt+rt)/2;
    if(md>=q) query(nod*2,lt,md,q,w,op);
    if(md<w) query(nod*2+1,md+1,rt,q,w,op);
}

void DI(int x,int y)
{
    if(x==y)
    {
        bestsum=max(bestsum,vr[x]-vr[x+1]);
        return;
    }
    int md=(x+y)/2;
    DI(x,md);
    DI(md+1,y);

    pre=-inf; suf=-inf;
    query(1,1,n,x,md,0);
    query(1,1,n,md+1,y,1);

    bestsum=max(bestsum,pre+suf-vl[n]);
}

int main()
{
    getline(f,s);
    n=nextint(); m=nextint();
    getline(f,s); ch=0;
    for(int i=1;i<=n;++i)
    {
        vl[i]=nextint();
        vr[i]=vl[i];
        vl[i]+=vl[i-1];
        build(1,1,n,i,1);
    }
    for(int i=n;i>=1;--i)
    {
        vr[i]+=vr[i+1];
        build(1,1,n,i,0);
    }
    for(int i=1;i<=m;++i)
    {
        getline(f,s); ch=0;
        a=nextint(); b=nextint();
        bestsum=-inf;
        DI(a,b);
        g<<bestsum<<'\n';
    }
    return 0;
}