#include <stdio.h>
#define int long long
#define MAXV 100000
#define MAXN 100000
#define LOGN 17
#define MAXP (1<<(LOGN+1))
int v[MAXN], lmax[MAXP], left[MAXP], right[MAXP], stot[MAXP];
int a, b, smax, sc;
inline int max2(int a, int b){
    if(a>=b){
        return a;
    }
    return b;
}
inline int max3(int a, int b, int c){
    return max2(max2(a, b), c);
}
void query(int p, int st, int dr){
    int m=(st+dr)/2;
    if((a<=st)&&(dr<=b)){
        smax=max2(smax, sc+left[p]);
        sc=max2(sc+stot[p], right[p]);
        smax=max3(smax, lmax[p], sc);
        return ;
    }
    if(a<=m){
        query(2*p+1, st, m);
    }
    if(b>m){
        query(2*p+2, m+1, dr);
    }
}
void dfs(int p, int st, int dr){
    int m=(st+dr)/2;
    if(st==dr){
        lmax[p]=left[p]=right[p]=stot[p]=v[st];
        return ;
    }
    dfs(2*p+1, st, m);
    dfs(2*p+2, m+1, dr);
    stot[p]=stot[2*p+1]+stot[2*p+2];
    left[p]=max2(left[2*p+1], stot[2*p+1]+left[2*p+2]);
    right[p]=max2(right[2*p+2], stot[2*p+2]+right[2*p+1]);
    lmax[p]=max3(lmax[2*p+1], lmax[2*p+2], left[2*p+2]+right[2*p+1]);
}
int main(){
    int n, q, i;
    FILE *fin, *fout;
    fin=fopen("sequencequery.in", "r");
    fout=fopen("sequencequery.out", "w");
    fscanf(fin, "%lld%lld", &n, &q);
    for(i=0; i<n; i++){
        fscanf(fin, "%lld", &v[i]);
    }
    dfs(0, 0, n-1);
    for(i=0; i<q; i++){
        fscanf(fin, "%lld%lld", &a, &b);
        a--;
        b--;
        sc=0;
        smax=-MAXV-1;
        query(0, 0, n-1);
        fprintf(fout, "%lld\n", smax);
    }
    fclose(fin);
    fclose(fout);
    return 0LL;
}