#include <iostream>
#include <fstream>
#include <algorithm>
#define nmax 400066
#define fs(i) i << 1
#define fd(i) (i << 1) + 1
using namespace std;

struct nod{
    long long s,pref,suf,r;
} A[nmax];

/*void update(int st,int dr,int i,int p,int v)
{
    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(st,mid,fs(i),p,v);
          else update(mid+1,dr,fd(i),p,v);

    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;
}*/

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

    int m = (l+r)>>1;
    if (p <= m) update(l, m, fs(i), p, v);
           else update(m + 1, r, fd(i), p, v);

    A[i].r=max(max(A[fs(i)].r, A[fd(i)].r), 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()
{
    int i,j,x,y,n,m;
    ifstream t1("sequencequery.in");
    ofstream t2("sequencequery.out");
    t1>>n>>m;
    for(i=1;i<=n;i++)
    {
        t1>>x;
        update(1,n,1,i,x);
    }

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

    t1.close();
    t2.close();
    return 0;
}