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