#include <bits/stdc++.h>

using namespace std;

ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

const long long inf=1000000000000;

int n,m,i,a[100010];

struct cons{
    long long Val_Lft=0,Val_Rgt=0,Bst=0;
    int Lft=0,Rgt=0;
}aint[400010];

cons ans;

cons marge(cons A,cons B)
{
    cons ret;
    ret.Lft=A.Lft;ret.Rgt=B.Rgt;

    ret.Val_Lft=max(A.Val_Lft,a[A.Rgt]-a[A.Lft-1]+B.Val_Lft);
    ret.Val_Rgt=max(B.Val_Rgt,a[B.Rgt]-a[B.Lft-1]+A.Val_Rgt);

    ret.Bst=max(max(A.Bst,B.Bst),A.Val_Rgt+B.Val_Lft);

    return ret;
}

void caut(int poz,int l,int r,int lo,int hi)
{
    if(lo<=l&&r<=hi)
    {
        //cout<<l<<' '<<r<<'\n';
        if(ans.Val_Lft!=-inf)
            ans=marge(ans,aint[poz]);
        else
            ans=aint[poz];
        return ;
    }
    int mi=(l+r)/2;
    if(lo<=mi)
        caut(poz*2  ,l   ,mi,lo,hi);
    if(mi+1<=hi)
        caut(poz*2+1,mi+1,r ,lo,hi);
    return;
}

void init(int poz,int l,int r)
{
    aint[poz].Lft=l;
    aint[poz].Rgt=r;
    if(l==r)
    {
        aint[poz].Val_Lft=aint[poz].Val_Rgt=aint[poz].Bst=a[l]-a[l-1];
        return ;
    }
    int mi=(l+r)/2;
    init(poz*2  ,l   ,mi);
    init(poz*2+1,mi+1,r );
    aint[poz]=marge(aint[poz*2],aint[poz*2+1]);
}

int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
        f>>a[i],a[i]+=a[i-1];
    init(1,1,n);
    for(;m;m--)
    {
        int x,y;
        f>>x>>y;
        if(x>y)swap(x,y);
        ans.Val_Lft=-inf;
        caut(1,1,n,x,y);
        g<<ans.Bst<<'\n';
    }
    return 0;
}