#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
ll mx[400002],mn[400002],a[400002],s[400002],l1,r1,ok;
void f(int l2,int r2,int nr)
{
    a[nr]=max(max(a[l2],a[r2]),mx[r2]-mn[l2]);
    mn[nr]=min(mn[l2],mn[r2]);
    mx[nr]=max(mx[l2],mx[r2]);
}
void querry(ll l2,ll r2,ll nr)
{
    if(l1<=l2&&r2<=r1)
    {
        if(!ok)
        {
            ok=1;
            a[0]=a[nr];
            mn[0]=mn[nr];
            mx[0]=mx[nr];
            return;
        }
        f(0,nr,0);
        return;
    }
    if(l2>=r2)
        return;
    ll m=(l2+r2)/2;
    if(m>=l1)
        querry(l2,m,nr*2);
    if(m<r2)
        querry(m+1,r2,nr*2+1);
}
void baga(ll l2,ll r2,ll nr)
{
    if(l2==r2)
    {
        mn[nr]=s[l2-1];
        mx[nr]=s[l2];
        a[nr]=mx[nr]-mn[nr];
        return;
    }
    if(l2>r2)
        return;
    ll m=(l2+r2)/2;
    baga(l2,m,nr*2);
    baga(m+1,r2,nr*2+1);
    f(nr*2,nr*2+1,nr);
}
int main()
{
    ll n,q,i;
    in>>n>>q;
    for(i=1;i<=n;i++)
    {
        in>>s[i];
        s[i]+=s[i-1];
    }
    baga(1,n,1);
    while(q--)
    {
        in>>l1>>r1;
        ok=0;
        querry(1,n,1);
        out<<a[0]<<"\n";
    }
    return 0;
}