//ATENTIE LA CITIRE!!!
#include <cstdio>
#include <algorithm>
#define nmax 100002
#define fiu_st nod*2
#define fiu_dr nod*2+1
#define ll long long
#define inf 987654321
using namespace std;

typedef struct{
    ll st, dr, tot, sum;
}camp;

camp t[nmax*4];
int n, m;
ll s, r;

void udpate(int nod, int st, int dr, int poz, int val){

    if (st == dr){
        t[nod].st = t[nod].dr = t[nod].tot = t[nod].sum = val;
        return;
    }else {
        int mij = (st + dr) / 2;
        if (poz <= mij) udpate(fiu_st, st, mij, poz, val);
                 else udpate(fiu_dr, mij+1, dr, poz, val);
    }

    t[nod].st = max(t[fiu_st].st, t[fiu_st].sum + t[fiu_dr].st);
    t[nod].dr = max(t[fiu_st].dr + t[fiu_dr].sum, t[fiu_dr].dr);
    t[nod].tot = max( max(t[fiu_st].tot, t[fiu_dr].tot), t[fiu_dr].st + t[fiu_st].dr );
    t[nod].sum = t[fiu_st].sum + t[fiu_dr].sum;

}

void query(int nod, int st, int dr, int a, int b){

    if (a <= st && b >= dr){
        if (s<0) s = 0;
        r = max(r, max(t[nod].st+s, t[nod].tot) );
        s = max(s + t[nod].sum, t[nod].dr);
        return;
    }else {
        int mij = (st + dr) / 2;
        if (a <= mij) query(fiu_st, st, mij, a, b);
        if (b > mij ) query(fiu_dr, mij+1, dr, a, b);
    }

}

void citire(){

    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    scanf("%d%d\n", &n, &m);
    for(int i=1; i<=n; i++) {
        int x;
        scanf("%d ", &x);
        udpate(1, 1, n, i, x);
    }

}

void rezolva(){

    for(int i=1; i<=m; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        r = s = -inf;
        query(1, 1, n, a, b);
        printf("%lld\n", r);
    }

}

int main(){

    citire();
    rezolva();
    return 0;
}