#include <iostream>
#include <cstdio>
#define nmax 400066
#define fs(i) i << 1
#define fd(i) (i << 1) + 1
#define ll long long
using namespace std;

struct nod
{
    ll s,pref,suf,r;
} a[nmax];

int n,m,x,y;

int maxim(ll a,ll b) { if(a<b) return b; else return a; }

int update(ll x,int i,int p,int st,int dr)
{
    if(st==dr)
    {
        a[i].s=a[i].pref=a[i].suf=a[i].r=x;
        return 1;
    }

    int mid=(st+dr)>>1;
    if(p<=mid) update(x,fs(i),p,st,mid);
          else update(x,fd(i),p,mid+1,dr);

    a[i].s=a[fs(i)].s+a[fd(i)].s;
    a[i].pref=maxim(a[fs(i)].pref,a[fs(i)].s+a[fd(i)].pref);
    a[i].suf=maxim(a[fd(i)].suf,a[fd(i)].s+a[fs(i)].suf);
    a[i].r=maxim(maxim(a[fs(i)].s,a[fd(i)].s),a[fs(i)].suf+a[fd(i)].pref);

}

nod solve(int st,int dr,int i)
{
    nod n1,n2,n3;
    int mid=(st+dr)>>1;

    if(st==dr)  return a[i];

    n1.s=n1.r=n1.pref=n1.suf=-0x3f3f3f3f3f;
    n2.s=n2.r=n2.pref=n2.suf=-0x3f3f3f3f3f;

    if(x<=mid) n1=solve(st,mid,fs(i));
    if(y>mid) n2=solve(mid+1,dr,fd(i));

    n3.r = maxim(maxim(n1.r, n2.r), n1.suf + n2.pref);
    n3.pref = maxim(n1.pref, n1.s + n2.pref);
    n3.suf = maxim(n2.suf, n2.s + n1.suf);
    n3.s = n1.s + n2.s;
    return n3;
}

int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        update(x,1,i,1,n);
    }

    nod node;
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        node=solve(1,n,1);
        printf("%lld\n",node.r);
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}