#include <iostream>

const int MAXN=(1<<18);
typedef long long ll;
const ll INF=1e18;

int sir[MAXN];

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

struct node{
    ll sum, prefmax, sufmax, sumsubsecvmax;
    node aduna(node a, node b){
        node aux;
        aux.sum=a.sum+b.sum;
        aux.prefmax=max(a.prefmax, a.sum+b.prefmax);
        aux.sufmax=max(b.sufmax, b.sum+a.sufmax);
        aux.sumsubsecvmax=max(max(a.sumsubsecvmax, b.sumsubsecvmax), a.sufmax+b.prefmax);
        return aux;
    }
};

struct SegmentTree{
    node tree[2*MAXN];
    int n;
    int get_p2(int n){
        while(n&(n-1))
            n+=n&-n;
        return n;
    }
    void init(int _n){
        int i;
        this->n=get_p2(_n);
        for(i=0; i<2*n; i++)
            tree[i]={-INF, -INF, -INF, -INF};
        for(i=n; i<n+_n; i++)
            tree[i]={sir[i-n], sir[i-n], sir[i-n], sir[i-n]};
        for(i=n-1; i>0; i--)
            tree[i]=tree[i].aduna(tree[i<<1], tree[i<<1|1]);
    }
    void update(int poz, int elem){
        poz+=n;
        tree[poz]={elem, elem, elem, elem};
        for(poz>>=1; poz>0; poz>>=1)
            tree[poz]=tree[poz].aduna(tree[poz<<1], tree[poz<<1|1]);
    }
    ll query(int l, int r){
        node ansl, ansr;
        l+=n;
        r+=n;
        ansl=ansr={-INF, -INF, -INF, -INF};
        while(l<=r){
            if((l&1))
                ansl=ansl.aduna(ansl, tree[l++]);
            l>>=1;
            if(!(r&1))
                ansr=ansl.aduna(tree[r--], ansr);
            r>>=1;
        }
        ansl=ansl.aduna(ansl, ansr);
        return ansl.sumsubsecvmax;
    }
};

SegmentTree aint;

int main(){
    FILE *fin, *fout;
    int n, i, q, l, r;
    fin=fopen("sequencequery.in", "r");
    fscanf(fin, "%d%d", &n, &q);
    for(i=0; i<n; i++)
        fscanf(fin, "%d", &sir[i]);
    aint.init(n);
    fout=fopen("sequencequery.out", "w");
    while(q--){
        fscanf(fin, "%d%d", &l, &r);
        fprintf(fout, "%lld\n", aint.query(l-1, r-1));
    }
    fclose(fin);
    fclose(fout);
    return 0;
}