#include <cstdio>
#define DN 400005
#define LL long long

LL a[DN],b[DN],c[DN],d[DN],sum,rez;
int n,m,gls,gld,poz,el;

static inline int max(LL a, LL b) {
    return a>b ? a:b;
}

static void update(int vn, int ls, int ld) {
    if(ls==ld) {
        a[vn]=b[vn]=c[vn]=d[vn]=el;
        return;
    }
    int m=(ls+ld)>>1,fs=vn<<1;
    if(poz<=m) update(fs,ls,m);
    else update(fs+1,m+1,ld);
    a[vn]=max(a[fs],d[fs]+a[fs+1]);
    b[vn]=max(b[fs]+d[fs+1],b[fs+1]);
    c[vn]=max(max(c[fs],c[fs+1]),b[fs]+a[fs+1]);
    d[vn]=d[fs]+d[fs+1];
}

static void query(int vn, int ls, int ld) {
    if(ls==ld) {
        if(0>sum) sum=0;
        rez=max(rez,max(sum+a[vn],c[vn]));
        sum=max(sum+d[vn],b[vn]);
        return;
    }
    int m=(ls+ld)>>1,fs=vn<<1;
    if(gls<=m) query(fs,ls,m);
    if(gld>m) query(fs+1,m+1,ld);
}

int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1; i<=n; ++i) {
        poz=i; scanf("%d",&el);
        update(1,1,n);
    }
    for(int i=1; i<=m; ++i) {
        sum=rez=-0x3f3f3f;
        scanf("%d %d",&gls,&gld);
        query(1,1,n);
        printf("%lld\n",rez);
    }
    return 0;
}