#include <cstdio>
#define MAXN 50000
long long ans, best, sum[4*MAXN], x[4*MAXN], y[4*MAXN], e[4*MAXN], a[MAXN+2], b[MAXN+1];
int v[MAXN+2], left, right;
inline long long max2(long long a, long long b){
    if(a>b){
        return a;
    }
    return b;
}
void dfs(int p, int st, int dr){
    if(st==dr){
        sum[p]=e[p]=v[st];
        if(v[st]>0){
            x[p]=v[st]+b[dr+1];
            y[p]=v[st]+a[st-1];
        }else{
            x[p]=b[dr+1];
            y[p]=a[st-1];
        }
    }else{
        int m=(st+dr)/2;
        dfs(2*p, st, m);
        dfs(2*p+1, m+1, dr);
        sum[p]=sum[2*p]+sum[2*p+1];
        e[p]=max2(x[2*p+1]+y[2*p], max2(e[2*p], e[2*p+1]));
        x[p]=max2(x[2*p], sum[2*p]+x[2*p+1]);
        y[p]=max2(y[2*p+1], sum[2*p+1]+y[2*p]);
    }
}
void query(int p, int st, int dr){
    if((left<=st)&&(dr<=right)){
        ans=max2(ans, max2(best+x[p], e[p]));
        best=max2(best+sum[p], y[p]);
    }else{
        int m=(st+dr)/2;
        if(left<=m){
            query(2*p, st, m);
        }
        if(m+1<=right){
            query(2*p+1, m+1, dr);
        }
    }
}
int main(){
    int n, m, i, x, y;
    long long sc;
    FILE *fin, *fout;
    fin=fopen("3max.in", "r");
    fout=fopen("3max.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=n; i++){
        fscanf(fin, "%d", &v[i]);
    }
    a[0]=0;
    sc=0;
    for(i=1; i<=n; i++){
        if(sc<0){
            sc=0;
        }
        sc+=v[i];
        if(a[i-1]>sc){
            a[i]=a[i-1];
        }else{
            a[i]=sc;
        }
    }
    b[n+1]=0;
    sc=0;
    for(i=n; i>=0; i--){
        if(sc<0){
            sc=0;
        }
        sc+=v[i];
        if(b[i+1]>sc){
            b[i]=b[i+1];
        }else{
            b[i]=sc;
        }
    }
    dfs(1, 2, n-1);
    for(i=1; i<=m; i++){
        fscanf(fin, "%d%d", &x, &y);
        if(x==1){
            x=2;
        }
        if(y==n){
            y=n-1;
        }
        if(x>y){
            fprintf(fout, "0\n");
        }else{
            left=x;
            right=y;
            ans=0;
            best=a[left-1];
            query(1, 2, n-1);
            fprintf(fout, "%lld\n", ans);
        }
    }
    fclose(fin);
    fclose(fout);
    return 0;
}