#include <iostream>
#include <climits>
#include <cstdio>
#define MAXN 100001
using namespace std;
struct arbore
{
    long long left,right,smax,tot;
}aint[4*MAXN];
int v[MAXN],x,y;
long long ans,t;
void dfs(int p,int st,int dr)
{
    if(st==dr)
        aint[p].left=aint[p].right=aint[p].smax=aint[p].tot=v[st];
    else
    {
        int mid=(st+dr)>>1;
        dfs(2*p,st,mid);
        dfs(2*p+1,mid+1,dr);
        long long val=max(aint[2*p].smax,aint[2*p+1].smax);
        aint[p].smax=max(val,aint[2*p].right+aint[2*p+1].left);
        aint[p].left=max(aint[2*p].left,aint[2*p].tot+aint[2*p+1].left);
        aint[p].right=max(aint[2*p+1].right,aint[2*p+1].tot+aint[2*p].right);
        aint[p].tot=aint[2*p].tot+aint[2*p+1].tot;
    }
}
void query(int p,int st,int dr)
{
    if(x<=st && dr<=y)
    {
        ans=max(ans,aint[p].smax);
        ans=max(ans,t+aint[p].left);
        t=max(t+aint[p].tot,aint[p].right);
    }
    else
    {
        int mid=(st+dr)>>1;
        if(x<=mid)
            query(2*p,st,mid);
        if(y>mid)
            query(2*p+1,mid+1,dr);
    }
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("sequencequery.in","r");
    fout=fopen("sequencequery.out","w");
    int n,m;
    fscanf(fin,"%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        fscanf(fin,"%d",&v[i]);
    dfs(1,1,n);
    for(int i=0;i<m;i++)
    {
        fscanf(fin,"%d%d",&x,&y);
        ans=LLONG_MIN,t=0;
        query(1,1,n);
        fprintf(fout,"%lld\n",ans);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}