#include<cstdio>
using namespace std;
struct arbint{long long left,right,best,sum;};
arbint arb[800000];
int v[200010],x,y;
long long answer,sum;
long long maxim(long long a,long long b){
    if(a<b)
        return b;
    return a;
}
void build_arbint(int node,int left,int right){
    int middle=(left+right)/2;
    if(left==right){
        arb[node].left=arb[node].right=arb[node].best=v[left];
        arb[node].sum=v[left];
        return;
    }
    build_arbint(2*node,left,middle);
    build_arbint(2*node+1,middle+1,right);
    arb[node].left=maxim(arb[2*node].left,arb[2*node].sum+arb[2*node+1].left);
    arb[node].right=maxim(arb[2*node+1].right,arb[2*node+1].sum+arb[2*node].right);
    arb[node].best=maxim(maxim(arb[2*node].best,arb[2*node+1].best),arb[2*node].right+arb[2*node+1].left);
    arb[node].sum=arb[2*node].sum+arb[2*node+1].sum;
}
void update(int node,int left,int right){
    int middle=(left+right)/2;
    if(left==right){
        arb[node].left=arb[node].right=arb[node].best=maxim(y,0);
        arb[node].sum=y;
        return;
    }
    if(x<=middle)
        update(2*node,left,middle);
    else
        update(2*node+1,middle+1,right);
    arb[node].left=maxim(arb[2*node].left,arb[2*node].sum+arb[2*node+1].left);
    arb[node].right=maxim(arb[2*node+1].right,arb[2*node+1].sum+arb[2*node].right);
    arb[node].best=maxim(maxim(arb[2*node].best,arb[2*node+1].best),arb[2*node].right+arb[2*node+1].left);
    arb[node].sum=arb[2*node].sum+arb[2*node+1].sum;
}
void query(int node,int left,int right){
    int middle=(left+right)/2;
    if(x<=left&&right<=y){
        if(sum<0)
            sum=0;
        answer=maxim(answer,maxim(sum+arb[node].left,arb[node].best));
        sum=maxim(sum+arb[node].sum,arb[node].right);
        return;
    }
    if(x<=middle)
        query(2*node,left,middle);
    if(y>=middle+1)
        query(2*node+1,middle+1,right);

}
int main(){
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    int n,m,i,op;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    build_arbint(1,1,n);
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        sum=0;
        answer=-2000000000;
        query(1,1,n);
        printf("%lld\n",answer);
    }
    return 0;
}