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

LL a[DN],b[DN],c[DN],d[DN],sum,rez;

inline LL max(LL x,LL y) { return x>y ? x:y; }

void update(int vn, int ls, int ld,int val,int poz) {
    if(ls==ld) {
        a[vn]=b[vn]=c[vn]=val;
        d[vn]=val;
        return;
    }
    int m=(ls+ld)>>1,fs=vn<<1;
    if(poz<=m) update(fs,ls,m,val,poz);
    else update(fs+1,m+1,ld,val,poz);
    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];
}

void query(int vn, int ls, int ld,int gls, int gld) {
    if(ls==ld) {
        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,gls,gld);
    if(gld>m) query(fs+1,m+1,ld,gls,gld);
}

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