#include <bits/stdc++.h>
#define Nmax 100005
#define ll long long
#define ls (nod<<1)
#define rs (ls+1)
#define DIM 70000
using namespace std;
char IN_buffer[DIM];
int IN_cursor=DIM-1;
template <class T>
void read(T &x)
{
    x=0;
    int sgn=1;
    while(!isdigit(IN_buffer[IN_cursor]))
    {
        if(IN_buffer[IN_cursor]=='-') sgn=-1;
        if(++IN_cursor==DIM)
        {
            IN_cursor=0;
            fread(IN_buffer,1,DIM,stdin);
        }
    }
    while(isdigit(IN_buffer[IN_cursor]))
    {
        x=x*10+IN_buffer[IN_cursor]-'0';
        if(++IN_cursor==DIM)
        {
            IN_cursor=0;
            fread(IN_buffer,1,DIM,stdin);
        }
    }
    x*=sgn;
}
ll s[Nmax];
#define s (s+1)
pair <int,int> Aint[Nmax<<2],ans;
int n,Q,lsh,rsh,i;
inline pair <int,int> maxim(const pair <int,int> &A, const pair <int,int> &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(int p, int q, int nod)
{
    if(p==q) Aint[nod]={p,q};
    else
    {
        int m=(p+q)>>1;
        build(p,m,ls);
        build(m+1,q,rs);
        Aint[nod]=maxim(Aint[ls],Aint[rs]);
    }
}
pair <int,int> query(int p, int q, int nod)
{
    if(lsh<=p and q<=rsh) return Aint[nod];
    else
    {
        int m=(p+q)>>1;
        pair <int,int> 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()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    read(n);
    read(Q);
    for(i=1;i<=n;i++)
    {
        read(s[i]);
        s[i]+=s[i-1];
    }
    build(1,n,1);
    while(Q--)
    {
        read(lsh);
        read(rsh);
        ans=query(1,n,1);
        printf("%lld\n",s[ans.second]-s[ans.first-1]);
    }

    return 0;
}