#include<bits/stdc++.h>
#define maxN 100005
#define INF 100005
using namespace std;
typedef struct tip
{
  int smax,st,dr,sum;
};
tip A[4*maxN+5],sol;
int v[maxN],n,m,a,b;
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        A[nod].smax=v[st];
        A[nod].st=v[st];
        A[nod].dr=v[st];
        A[nod].sum=v[st];
    }
    else
    {
        int mid=(st+dr)>>1;
        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);
        A[nod].smax=max(max(A[2*nod].smax,A[2*nod+1].smax),A[2*nod].dr+A[2*nod+1].st);
        A[nod].sum=A[2*nod].sum+A[2*nod+1].sum;
        A[nod].st=max(A[2*nod].st,A[2*nod].sum+A[2*nod+1].st);
        A[nod].dr=max(A[2*nod+1].dr,A[2*nod+1].sum+A[2*nod].dr);
    }
}

void query(int nod,int st,int dr,int a,int b)
{
    if(a<=st && dr<=b)
    {
        if(sol.sum==-INF)
        {
            sol=A[nod];
        }
        else
        {
            sol.smax = max(sol.smax, max(A[nod].smax, sol.dr + A[nod].st ));
            sol.dr = max(A[nod].dr, A[nod].sum + sol.dr);
        }
    } else {
       int mid=(st+dr)>>1;
        if(a<=mid) query(2*nod,st,mid,a,b);
        if(b>mid) query(2*nod+1,mid+1,dr,a,b);
    }
}
int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&v[i]);
    }
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        sol.sum=-INF;
        query(1,1,n,a,b);
        printf("%d\n",sol.smax);
    }
    return 0;
}