#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;

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 A,int b,int i)
{
    if(st>=A && dr<=b)
            return a[i];

    nod v1,v2,v3;
    int mid=(st+dr)>>1;

    v1.s=v1.r=v1.pref=v1.suf=-500000;
    v2.s=v2.r=v2.pref=v2.suf=-500000;

    if(A<=mid) v1=solve(st,mid,A,b,fs(i));
    if(b>mid) v2=solve(mid+1,dr,A,b,fd(i));

    v3.r = max(max(v1.r, v2.r), v1.suf + v2.pref);
    v3.pref = max(v1.pref, v1.s + v2.pref);
    v3.suf = max(v2.suf, v2.s + v1.suf);
    v3.s = v1.s + v2.s;
    return v3;
}

int main()
{
    ifstream t1("sequencequery.in");
    ofstream t2("sequencequery.out");
    int i,j,x,y;
    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,x,y,1);
        t2<<node.r<<'\n';
    }

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