#include <bits/stdc++.h>
#define Nmax 100005
#define ll long long
#define ls (nod<<1)
#define rs (ls+1)
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
ll s[Nmax];
pair <ll,ll> Aint[Nmax<<2],ans;
ll n,Q,lsh,rsh,i;
inline pair <ll,ll> maxim(const pair <ll,ll> &A, const pair <ll,ll> &B)
{
    ll s1,s2,s3,maxx;
    if(!(A.first*A.second)) return B;
    if(!(B.first*B.second)) return A;
    s1=s[A.second]-s[A.first-1];
    s2=s[B.second]-s[B.first-1];
    s3=s[B.second]-s[A.first-1];
    maxx=max(s1,max(s2,s3));
    if(s1==maxx) return A;
    if(s2==maxx) return B;
    return {A.first,B.second};
}
void build(ll p, ll q, ll nod)
{
    if(p==q) Aint[nod]={p,q};
    else
    {
        ll m=(p+q)>>1;
        build(p,m,ls);
        build(m+1,q,rs);
        Aint[nod]=maxim(Aint[ls],Aint[rs]);
    }
}
pair <ll,ll> query(ll p, ll q, ll nod)
{
    if(lsh<=p and q<=rsh) return Aint[nod];
    else
    {
        ll m=(p+q)>>1;
        pair <ll,ll> max1,max2;
        max1=max2={0,0};
        if(lsh<=m) max1=query(p,m,ls);
        if(m<rsh) max2=query(m+1,q,rs);
        return maxim(max1,max2);
    }
}
int main()
{
    f>>n>>Q;
    for(i=1;i<=n;i++)
    {
        f>>s[i];
        s[i]+=s[i-1];
    }
    build(1,n,1);
    while(Q--)
    {
        f>>lsh>>rsh;
        ans=query(1,n,1);
        g<<s[ans.second]-s[ans.first-1]<<'\n';
    }

    return 0;
}