#include <stdio.h>
#include <stdlib.h>
#define MAXN 100000

#define BUF_SIZE 16384
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline long long nextnum(){
    long long a=0;
    char c=nextch();
    while((c<'0' || c>'9') && c!='-')
        c=nextch();
    int semn=1;
    if(c=='-'){
        semn=-1;
        c=nextch();
    }
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a*semn;
}

long long w[MAXN+1];
struct FraxinusPennsylvanicaVarSubintegerrima{
    long long suff, pref, sum, seq;
} v[4*MAXN];///pentru persoanele curioase, care nu ar trebui sa imi citeasca sursa, aista ii nume de pom, sau cum le place unora sa zica, arbore de intervale

inline long long maxim(long long a, long long b){
    return a > b ? a : b;
}
inline long long maxim3(long long a, long long b, long long c){
    if(a>maxim(b, c))
        return a;
    return b > c ? b : c;
}

void parcurgere(int p, int st, int dr){
    if(st==dr)
        v[p].suff=v[p].pref=v[p].sum=v[p].seq=w[st];
    else{
        parcurgere(2*p, st, (st+dr)/2);
        parcurgere(2*p+1, (st+dr)/2+1, dr);
        v[p].sum=v[2*p].sum+v[2*p+1].sum;
        v[p].suff=maxim(v[2*p+1].sum+v[2*p].suff, v[2*p+1].suff);
        v[p].pref=maxim(v[2*p].sum+v[2*p+1].pref, v[2*p].pref);
        v[p].seq=maxim3(v[2*p].seq, v[2*p+1].seq, v[2*p].suff+v[2*p+1].pref);
    }
}

int left, right;
long long rez;
long long partial;
void query(int p, int st, int dr){
    //printf("%d %d   %d %d %d\n", left, right, p, st, dr);
    if(left<=st && dr<=right){
        if(0>partial) partial=0;
        rez=maxim3(rez, v[p].seq, partial+v[p].pref);
        partial=maxim(v[p].suff, partial+v[p].sum);
    }
    else{
        int m=(st+dr)/2;
        if(left<=m) query(2*p, st, m);
        if(m<right) query(2*p+1, m+1, dr);
    }
}

int main(){
    fi=fopen("sequencequery.in","r");
    fo=fopen("sequencequery.out","w");
    int n=nextnum(), m=nextnum();
    for(int i=1;i<=n;i++)
        w[i]=nextnum();
    parcurgere(1, 1, n);
    for(int i=0;i<m;i++){
        left=nextnum();
        right=nextnum();
        partial=0LL;
        rez=-1000000000;
        query(1, 1, n);
        fprintf(fo,"%lld\n", rez);
    }
    fclose(fi);
    fclose(fo);
    return 0;
}