#include <iostream>
#include <fstream>
#include <algorithm>
#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; }

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

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

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

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

//    if (l >= a && r <= b)
    if(st>=x && dr<=y)  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()
{
    ifstream t1("sequencequery.in");
    ofstream t2("sequencequery.out");
    int i,j;
    t1>>n>>m;
    for(i=1;i<=n;i++)
    {
        t1>>x;
        update(x,1,i,1,n);
    }

    nod node;
    for(i=1;i<=m;i++)
    {
        t1>>x>>y;
        node=solve(1,n,1);
        t2<<node.r<<'\n';
    }

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