#include<fstream>
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
const long long inf=1<<25;
struct pie
{
    long long s,l,r,m;
}tree[400010];
int n,m;
int v[100005];
long long dp,solution;
void build(int node,int l,int r)
{
    if(l==r)
    {
        tree[node].s=v[l];//suma intregului interval
        tree[node].l=v[l];//suma in stanga
        tree[node].r=v[l];//suma in dreapta
        tree[node].m=v[l];//suma in mijloc
        return;
    }
    int mij=(l+r)/2;
    int ls=2*node,lr=ls+1;
    build(ls,l,mij);
    build(lr,mij+1,r);
    tree[node].s=tree[ls].s+tree[lr].s;
    tree[node].l=max(tree[ls].l,tree[ls].s+tree[lr].l);
    tree[node].r=max(tree[lr].r,tree[ls].r+tree[lr].s);
    tree[node].m=max(max(tree[ls].m,tree[lr].m),tree[ls].r+tree[lr].l);
}
void query(int node,int l,int r,int ql,int qr)//subsecvente de suma maxima pe intervalul [ql,qr]
{
    if(qr<l||r<ql)//ies din interval
      return;
    if(l>=ql&&qr>=r)//ma afluu in interval
    {
        solution=max(solution,max(tree[node].m,dp+tree[node].l));
        dp=max(dp+tree[node].s,tree[node].r);
        return;
    }
    int mij=(l+r)/2;
    int ls=2*node,lr=ls+1;
    query(ls,l,mij,ql,qr);
    query(lr,mij+1,r,ql,qr);
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=n;++i)
      f>>v[i];
    build(1,1,n);
    while(m--)
    {
        int st,dr;
        f>>st>>dr;
        dp=-inf,solution=-inf;
        query(1,1,n,st,dr);
        g<<solution<<"\n";
    }
    return 0;
}