# include <bits/stdc++.h>
using namespace std;
ifstream fi("sequencequery.in");
ofstream fo("sequencequery.out");
const int nmax = 1e5 + 5;
long long v[nmax];
long long ans,mins;
struct arb
{
    long long sumb,suma,ans;
} s[nmax<<2];
arb comb(arb a,arb b)
{
    arb r;
    r.ans = max(max(a.ans,b.ans),b.sumb - a.suma);
    r.suma = min(a.suma,b.suma);
    r.sumb = max(a.sumb,b.sumb);
    return r;
}
void built(int p,int u,int nod)
{
    if (p > u) return;
    if (p == u)
    {
        s[nod].ans = v[p] - v[p-1];s[nod].sumb = v[p];s[nod].suma = v[p-1];
    }
    else
    {
        int m = (p + u)>>1;
        built(p,m,nod<<1);
        built(m+1,u,(nod<<1)+1);
        s[nod] = comb(s[nod<<1],s[(nod<<1)+1]);
    }
}
void query(int p,int u,int st,int dr,int nod)
{
    if (p > u) return;
    if (st <= p && u <= dr)
    {
        ans = max(ans,max(s[nod].ans,s[nod].sumb - mins));
        mins = min(mins,s[nod].suma);
    }
    else
    {
        int m = (p + u)>>1;
        if (st <= m) query(p,m,st,dr,nod<<1);
        if (dr >  m) query(m+1,u,st,dr,(nod<<1)+1);
    }
}
int main(void)
{
    int n,m,x,y;
    fi>>n>>m;
    for (int i=1;i<=n;++i) fi>>v[i],v[i] += v[i-1];
    built(1,n,1);
    while (m --)
    {
        fi>>x>>y;
        ans = -1e19;mins=1e19;
        query(1,n,x,y,1);
        fo << ans << '\n';
    }
    return 0;
}