#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    int ras;
    int pref;
    int suf;
    int sum;
}aint[400005];
int v[100005];
void build(int node, int st, int dr){
    if(st==dr){
        aint[node].sum=v[st];
        aint[node].pref=v[st];
        aint[node].suf=v[st];
        aint[node].ras=v[st];
    }
    else{
        int mid=(st+dr)/2;
        build(2*node, st, mid);
        build(2*node+1, mid+1, dr);
        aint[node].pref=max(aint[2*node].pref, max(aint[2*node].sum, max(aint[2*node].sum+aint[2*node+1].pref, aint[2*node].sum+aint[2*node+1].sum)));
        aint[node].suf=max(aint[2*node+1].suf, max(aint[2*node+1].sum, max(aint[2*node+1].sum+aint[2*node].suf, aint[2*node].sum+aint[2*node+1].sum)));
        aint[node].ras=max(aint[2*node].pref, max(aint[2*node].sum, max(aint[2*node].sum+aint[2*node+1].pref, aint[2*node].sum+aint[2*node+1].sum)));
        aint[node].ras=max(aint[node].ras, max(aint[2*node+1].suf, max(aint[2*node+1].sum, aint[2*node+1].sum+aint[2*node].suf)));
        aint[node].ras=max(aint[node].ras, max(aint[2*node].ras, aint[2*node+1].ras));
        aint[node].ras=max(aint[node].ras, aint[2*node].suf+aint[2*node+1].pref);
        aint[node].sum=aint[2*node].sum+aint[2*node+1].sum;                                                                               
    }
}
node max1;
int ok=0;
void query(int node, int st, int dr, int a, int b){
    if(a<=st && dr<=b){
        if(ok==1){
            max1.ras=max(max1.ras, max(aint[node].ras, max(max1.sum, max(aint[node].sum, max1.sum+aint[node].sum))));
            max1.ras=max(max1.ras, max(max1.pref, max1.sum+aint[node].pref));
            max1.ras=max(max1.ras, max(aint[node].suf, aint[node].sum+max1.suf));
            max1.ras=max(max1.ras, max1.suf+aint[node].pref);
            max1.pref=max(max1.pref, max(max1.sum, max(max1.sum+aint[node].pref, max1.sum+aint[node].sum)));
            max1.suf=max(aint[node].suf, max(aint[node].sum, max(aint[node].sum+max1.suf, aint[node].sum+max1.sum)));
            max1.sum=max1.sum+aint[node].sum;   
        }
        else{
            ok=1;
            max1.pref=aint[node].pref; 
            max1.suf=aint[node].suf;
            max1.sum=aint[node].sum;
            max1.ras=aint[node].ras;
        }
    }
    else{
        int mid=(st+dr)/2;
        if(a<=mid)
            query(2*node, st, mid, a, b);
        if(mid+1<=b)
            query(2*node+1, mid+1, dr, a, b);
    }
}
int32_t main(){
    ifstream cin ("sequencequery.in");
    ofstream cout ("sequencequery.out");
    int n, q, a, b;
    cin >> n >> q;
    for(int i=1; i<=n; i++)
        cin >> v[i];
    build(1, 1, n);
    for(int i=1; i<=q; i++){
        cin >> a >> b;
        ok=0;
        max1.ras=max1.pref=max1.suf=-10000000000;
        max1.sum=0;
        query(1, 1, n, a, b);
        cout << max1.ras << '\n';
    }
    return 0;
}