#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define fast ios_base::sync_with_stdio(0);f.tie(0);g.tie(0);
#define setinf(x) memset(x,63,sizeof(x));
#define set0(x) memset(x,0,sizeof(x));
#define all(x) x.begin(),x.end()
#define tiii tuple<int,int,int>
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define vll vector<ll>
#define pb push_back
#define fi first
#define se second
#define DD 100001
#define nl '\n'
using namespace std;
const string file="sequencequery";
ifstream f(file+".in");
ofstream g(file+".out");
//#define f cin
//#define g cout
struct  aint {
    struct xy {
        ll s,smax,pf,sf;
    };
    vector<xy> v;
    int n;
    aint(int _n) {
        n=_n;
        v.resize(n*4);
    }
    xy comb(xy st, xy dr) {
        xy x;
        x.s=st.s+dr.s;
        x.pf=max(st.pf,st.s+dr.pf);
        x.sf=max(dr.sf,dr.s+st.sf);
        x.smax=max({st.smax,dr.smax,st.sf+dr.pf});
        return x;
    }
    void build(int nod, int st, int dr) {
        if (st==dr) {
            int x;
            f>>x;
            v[nod].s=v[nod].pf=v[nod].sf=v[nod].smax=x;
            return;
        }
        int mid=(st+dr)>>1;
        build(nod*2,st,mid);
        build(nod*2+1,mid+1,dr);
        v[nod]=comb(v[nod*2],v[nod*2+1]);
    }
    xy query(int nod, int st, int dr, int l, int r) {
        if (l<=st && dr<=r) return v[nod];
        int mid=(st+dr)>>1;
        if (r<=mid) return query(nod*2,st,mid,l,r);
        if (l>mid) return query(nod*2+1,mid+1,dr,l,r);
        xy L=query(2*nod,st,mid,l,r);
        xy R=query(2*nod+1,mid+1,dr,l,r);
        return comb(L,R);
    }
};
int main(){
    int n,q;
    f>>n>>q;
    aint v(n);
    v.build(1,1,n);
    while(q--) {
        int x,y;
        f>>x>>y;
        g<<v.query(1,1,n,x,y).smax<<nl;
    }
    system("pause");
    return 0;
}