#include <algorithm>
#include <fstream>
#include <cstring>

using namespace std;

const int N=100005;
const long long INF=(1LL<<61);

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

int x, y;
long long a[N], b[N], c[N], d[N], s, sol;

void update(int nod, int l, int r)
{
    if(l==r)
    {
        a[nod]=b[nod]=c[nod]=y;
        d[nod]=y;
        return;
    }
    int mid=(l+r)/2;
    if(x<=mid) update(2*nod, l, mid);
    else update(2*nod+1, mid+1, r);
    a[nod]=max(a[2*nod], d[2*nod]+a[2*nod+1]);
    b[nod]=max(b[2*nod+1], b[2*nod]+d[2*nod+1]);
    c[nod]=max(max(c[2*nod], c[2*nod+1]), b[2*nod]+a[2*nod+1]);
    d[nod]=d[2*nod]+d[2*nod+1];
}

void query(int nod, int l, int r)
{
    if(x<=l&&r<=y)
    {
        if(s<0) s=0;
        sol=max(sol, max(s+a[nod], c[nod]));
        s=max(s+d[nod], b[nod]);
        return;
    }
    int mid=(l+r)/2;
    if(x<=mid) query(2*nod, l, mid);
    if(y>mid) query(2*nod+1, mid+1, r);
}

int main()
{
    int n, m, i;
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>y;
        x=i;
        update(1, 1, n);
    }
    while(m--)
    {
        s=0;
        sol=-INF;
        fin>>x>>y;
        query(1, 1, n);
        fout<<sol<<"\n";
    }
}