#include <bits/stdc++.h>
#define inf -1e11
using namespace std;
struct ura
{
    int pozmin,pozmax;
    long long val;
}ab[400001];
long long sp[100001];
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        ab[nod].val=sp[st]-sp[st-1];
        ab[nod].pozmax=st;
        ab[nod].pozmin=st-1;
    }
    else
    {
        int mij=(st+dr)/2;
        build(nod*2,st,mij);
        build(nod*2+1,mij+1,dr);
        ab[nod].val=max(ab[nod*2].val,ab[nod*2+1].val);
        ab[nod].val=max(ab[nod].val,sp[ab[nod*2+1].pozmax]-sp[ab[nod*2].pozmin]);
        if(sp[ab[nod*2].pozmin]<sp[ab[nod*2+1].pozmin])
            ab[nod].pozmin=ab[nod*2].pozmin;
        else
            ab[nod].pozmin=ab[nod*2+1].pozmin;
        if(sp[ab[nod*2].pozmax]>sp[ab[nod*2+1].pozmax])
            ab[nod].pozmax=ab[nod*2].pozmax;
        else
            ab[nod].pozmax=ab[nod*2+1].pozmax;
    }
}
long long rez;
int a,b,poz;
void query(int nod, int st, int dr)
{
    if(a<=st&&dr<=b)
    {
        rez=max(max(rez,sp[ab[nod].pozmax]-sp[poz]),ab[nod].val);
        if(sp[ab[nod].pozmin]<sp[poz])
            poz=ab[nod].pozmin;
    }
    else
    {
        int mij=(st+dr)/2;
        if(a<=mij)
            query(nod*2,st,mij);
        if(b>mij)
            query(nod*2+1,mij+1,dr);
    }
}
int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    ios :: sync_with_stdio(false);
    cin.tie(0);
    int n,m,i;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    {
        cin>>sp[i];
        sp[i]+=sp[i-1];
    }
    sp[0]=-inf;
    build(1,1,n);
    for(i=1;i<=m;i++)
    {
        cin>>a>>b;
        rez=inf;
        poz=0;
        query(1,1,n);
        cout<<rez<<'\n';
    }
    return 0;
}