/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;

struct nod
{
    long long pref;
    long long suff;
    long long ssm;
    long long total;
};

const long long inf = 1e13;
const nod neginf={-inf,-inf,-inf,-inf};

int v[100001];
nod aint[400001];

void combine(nod &a, const nod &s, const nod&d)
{
    a.total=s.total+d.total;
    a.pref=max(s.total+d.pref,s.pref);
    a.suff=max(d.total+s.suff,d.suff);
    a.ssm=max(s.suff+d.pref,s.ssm);
    a.ssm=max(a.ssm,d.ssm);
}

void build(const int &st, const int &dr, const int &val)
{
    if (st==dr)
    {
        aint[val].pref=v[st];
        aint[val].suff=v[st];
        aint[val].ssm=v[st];
        aint[val].total=v[st];
        return;
    }
    int mid;
    mid=(st+dr)/2;
    build(st,mid,val*2);
    build(mid+1,dr,val*2+1);
    combine(aint[val],aint[val*2],aint[val*2+1]);
}

nod query (const int &st, const int &dr, const int &qa, const int &qb, const int &val)
{
    if (qa<=st && dr<=qb)
        return aint[val];
    if (qa>dr || qb<st)
        return neginf;
    int mid;
    mid=(st+dr)/2;
    nod l,r,ans;
    l=neginf;
    r=neginf;
    ans=neginf;
    if (qa<=mid)
        l=query(st,mid,qa,qb,val*2);
    if (qb>mid)
        r=query(mid+1,dr,qa,qb,val*2+1);
    combine(ans,l,r);
    return ans;
}

int main()
{
    ifstream fin("sequencequery.in");
    ofstream fout("sequencequery.out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,i,j,q,l,r;
    fin >> n >> q;
    for (i=1; i<=n; i++)
    {
        fin >> v[i];
    }
    build(1,n,1);
    for (i=1; i<=q; i++)
    {
        fin >> l >> r;
        fout << query(1,n,l,r,1).ssm << "\n";
    }
}