#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
#define MAX 401010
struct node{
    long long ma, mi, sub;
    bool operator ==(node x)
    {
        if(this->ma==x.ma && this->mi==x.mi && this->sub==x.sub)
            return 1;
        return 0;
    }

};

node a[MAX], nul;

void update(long long nod)
{
    if(!nod)
        return;
    a[nod].ma=max(a[nod<<1].ma, a[(nod<<1)+1].ma);
    a[nod].mi=min(a[nod<<1].mi, a[(nod<<1)+1].mi);
    a[nod].sub=max(a[nod<<1].sub, max(a[(nod<<1)+1].sub, a[(nod<<1)+1].ma-a[nod<<1].mi));
    update(nod>>1);
}

node query(long long a, long long b, long long st, long long dr, long long nod)
{
    if(b<st || dr<a)
        return nul;
    if(a<=st && dr<=b)
    {

        return ::a[nod];
    }
    node f, g, v;
    long long mid=(st+dr)>>1;

    f=query(a, b, st, mid, nod<<1);
    g=query(a, b, mid+1, dr, (nod<<1)+1);
    if(f==nul)
        return g;

    if(g==nul)
        return f;

    v.ma=max(f.ma, g.ma);
    v.mi=min(f.mi, g.mi);
    v.sub=max(f.sub, max(g.sub, g.ma-f.mi));
    return v;
}

int main()
{
    long long n, m, cn, i, x, y;
    fin>>n>>m;
    cn=n;
    if(cn&(cn-1))
    {
        while(cn&(cn-1))
        {
            cn&=(cn-1);
        }
        cn<<=1;
    }
    long long s=0;
    for(i=0;i<n;i++)
    {
        fin>>x;
        s+=x;
        a[cn+i].sub=x;
        a[cn+i].ma=s;
        a[cn+i].mi=s-x;
        update((cn+i)/2);

    }
    n=cn;
    while(m--)
    {
        fin>>x>>y;
        fout<<query(x, y, 1, cn, 1).sub<<"\n";
    }

}