// #pragma GCC optimize("O3,unroll-loops,fast-math")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;

const int Nmax=2e5+5,inf=1e9,MOD=1e9+7;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

struct AINT {
    struct Node {
        int sum,pref,suff,ssm;
    };
    int n;
    vector<Node> aint;
    void init(int _n) {
        n=_n;
        aint.resize(4*n+5);
    }
    void push(int node) {
        aint[node].sum=aint[2*node].sum+aint[2*node+1].sum;
        aint[node].pref=max(aint[2*node].pref,aint[2*node].sum+aint[2*node+1].pref);
        aint[node].suff=max(aint[2*node+1].suff,aint[2*node+1].sum+aint[2*node].suff);
        aint[node].ssm=max({aint[2*node].ssm,aint[2*node+1].ssm,aint[2*node].suff+aint[2*node+1].pref});
    }
    void build(int node, int st, int dr) {
        if (st==dr) {
            int x;
            fin>>x;
            aint[node]={x,x,x,x};
            return;
        }
        int mij=(st+dr)/2;
        build(2*node,st,mij);
        build(2*node+1,mij+1,dr);
        push(node);
    }
    Node merge(Node a, Node b) {
        Node rez;
        rez.sum=a.sum+b.sum;
        rez.pref=max(a.pref,a.sum+b.pref);
        rez.suff=max(b.suff,b.sum+a.suff);
        rez.ssm=max({a.ssm,b.ssm,a.suff+b.pref});
        return rez;
    }
    Node query(int node, int st, int dr, int l, int r) {
        if (st>=l && dr<=r) return aint[node];
        int mij=(st+dr)/2;
        if (l>mij) return query(2*node+1,mij+1,dr,l,r);
        if (r<=mij) return query(2*node,st,mij,l,r);
        return merge(query(2*node,st,mij,l,r),query(2*node+1,mij+1,dr,l,r));
    }
} aint;

signed main() {
    
    int n,t;
    fin>>n>>t;
    aint.init(n);
    aint.build(1,1,n);
    while (t--) {
        int x,y;
        fin>>x>>y;
        fout<<aint.query(1,1,n,x,y).ssm<<"\n";
    }
    return 0;
}