#include <fstream>

using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
typedef long long ll;
struct node{
    ll lmax = -1e9,rmax = -1e9,maxx = -1e9,sum = 0;
    int sbn = -1e9;
};
int v[100000];
node v2[400000];
int n,i,q;
node combine(node l,node r){
    node ans;
    ans.lmax = max(r.lmax,l.lmax + r.sum);
    ans.rmax = max(l.rmax,r.rmax + l.sum);
    ans.maxx = max(max(l.maxx,r.maxx),l.lmax + r.rmax);
    ans.sum = l.sum + r.sum;
    ans.sbn = max(l.sbn,r.sbn);
    return ans;
}
void tree(int l,int r,int cur = 1){
    if(l == r){
        v2[cur] = {max(v[l],0),max(v[l],0),max(v[l],0),v[l],v[l]};
    }else{
        int mij = (l + r)/2;
        tree(l,mij,cur*2);
        tree(mij + 1,r,cur*2 + 1);
        v2[cur] = combine(v2[cur*2],v2[cur*2 + 1]);
    }
    //cout<<v2[cur].lmax<<' '<<v2[cur].rmax<<' '<<v2[cur].maxx<<' '<<v2[cur].sum<<' '<<l<<' '<<r<<'\n';
}
node query(int l,int r,int cur = 1,int l2 = 0,int r2 = n - 1){
    //cout<<l<<' '<<r<<' '<<l2<<' '<<r2<<' ';
    node ans;
    if(r2 < l || r < l2){
        ///outside
        //cout<<"out\n";
        ans = {-1,-1,-1,-1,-1};
    }else if(l <= l2 && r2 <= r){
        ///inside
        //cout<<"in\n";
        ans = v2[cur];
    }else{
        ///partial
        //cout<<"pp\n";
        int mij = (l2 + r2)/2;
        node left = query(l,r,cur*2,l2,mij);
        node right = query(l,r,cur*2 + 1,mij + 1,r2);
        if(left.lmax == -1){
            ans = right;
        }else if(right.lmax == -1){
            ans = left;
        }else{
            ans = combine(left,right);
        }
    }
    //cout<<l2<<' '<<r2<<' '<<ans.lmax<<' '<<ans.rmax<<' '<<ans.maxx<<' '<<ans.sum<<'\n';
    return ans;
}
int main()
{
    node ans;
    int l,r;
    fin>>n>>q;
    for(i = 0;i < n;i++){
        fin>>v[i];
    }
    tree(0,n - 1);
    for(i = 0;i < q;i++){
        fin>>l>>r;
        ans = query(l - 1,r - 1);
        if(ans.maxx == 0)ans.maxx = ans.sbn;
        fout<<ans.maxx<<'\n';
    }
    return 0;
}