#include <cstdio>
#include <algorithm>
using namespace std;

int S,  pos, Sol, n, m, a, b, x[400089], A[400089], B[400089], C[400089], Sum[400089];
inline void Build(int st, int dr, int nod){
    if(st == dr){A[nod] = B[nod] = C[nod] = x[st]; Sum[nod] = x[st]; return ;}
    int mid = (st + dr) / 2;
    Build(st, mid, nod * 2);
    Build(mid + 1, dr, nod * 2 + 1);
    A[nod] = max(A[nod * 2], Sum[nod * 2] + A[nod * 2 + 1]);
    B[nod] = max(B[nod * 2] + Sum[nod * 2 + 1], B[nod * 2 + 1]);
    C[nod] = max(max(C[nod * 2 + 1], C[nod * 2]), B[nod * 2] + A[nod * 2 + 1]);
    Sum[nod] = Sum[nod * 2] + Sum[nod * 2 + 1];
}
inline void Query(int st, int dr, int nod){
    if(a <= st && dr <= b) {
        Sol = max(Sol, max(S + A[nod], C[nod]));
        S = max(S + Sum[nod], B[nod]);
        return ;
    }
    int mid = (st + dr) / 2;
    if(mid >= a) Query(st, mid, nod * 2);
    if(mid < b) Query(mid + 1, dr, nod * 2 + 1);
}
int main()
{
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n ; ++i)
        scanf("%d", &x[i]);
    Build(1, n, 1);
    for(int i = 1; i <= m ; ++i){
        scanf("%d%d", &a, &b); S = 0;
        Sol = -2000000000; Query(1, n, 1);
        printf("%d\n", Sol);
    }
    return 0;
}