# include <bits/stdc++.h>
# define max3(a,b,c) max(max(a,b),c)
# define ll long long
using namespace std;
const ll oo = 1e10 + 5;
const int nmax = 1e6 + 5;
ll a[nmax],b[nmax],c[nmax],d[nmax],ans,aux;
int s[nmax],n,m;
void update(int node,int p,int u)
{
    if (p == u) {a[node]=b[node]=c[node]=d[node]=s[p];return;}
    int m=(p+u)/2;
    update(node*2,p,m);
    update(node*2+1,m+1,u);
    a[node]=max(a[2*node],d[2*node]+a[2*node+1]);
    b[node]=max(b[2*node+1],d[2*node+1]+b[2*node]);
    c[node]=max3(c[2*node],c[2*node+1],b[2*node]+a[2*node+1]);
    d[node]=d[2*node]+d[2*node+1];
}
void query(int node,int p,int u,int s,int f)
{
    if (s<=p && u<=f)
    {
        ans=max3(ans,aux+a[node],c[node]);
        aux=max(d[node]+aux,b[node]);
        return;
    }
    int m=(p+u)/2;
    if (s<=m) query(2*node,p,m,s,f);
    if (f> m) query(2*node+1,m+1,u,s,f);
}
int main(void)
{
    ifstream fi("sequencequery.in");
    ofstream fo("sequencequery.out");
    fi>>n>>m;
    for (int i=1;i<=n;++i) fi>>s[i];
    update(1,1,n);
    for (int x,y;m;--m)
    {
        fi>>x>>y;
        aux=0;ans=-oo;
        query(1,1,n,x,y);
        fo << ans << '\n';
    }
    return 0;
}