# include <cstdio>

const char *FIN = "sequencequery.in", *FOU = "sequencequery.out";
const int MAX = 1 << 18, MAX_A = 1 << 19;

int N, T, V[MAX];
long long A[MAX_A], B[MAX_A], C[MAX_A], D[MAX_A], sum, sol;

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

void buildtree (int nod, int st, int dr) {
    if (st == dr) {
        A[nod] = B[nod] = C[nod] = D[nod] = V[st];
        return ;
    }
    int mij = st + dr >> 1;
    buildtree (nod << 1, st, mij);
    buildtree ((nod << 1) + 1, mij + 1, dr);
    A[nod] = max (A[nod << 1], D[nod << 1] + A[(nod << 1) + 1]);
    B[nod] = max (B[nod << 1] + D[(nod << 1) + 1], B[(nod << 1) + 1]);
    C[nod] = max (max (C[nod << 1], C[(nod << 1) + 1]), B[nod << 1] + A[(nod << 1) + 1]);
    D[nod] = D[nod << 1] + D[(nod << 1) + 1];
}

void query (int nod, int st, int dr, int s1, int s2) {
    if (s1 <= st && dr <= s2) {
        sum = max (sum, 0);
        sol = max (sol, max (sum + A[nod], C[nod]));
        sum = max (sum + D[nod], B[nod]);
        return ;
    }
    int mij = st + dr >> 1;
    if (s1 <= mij) query (nod << 1, st, mij, s1, s2);
    if (s2 > mij)  query ((nod << 1) + 1, mij + 1, dr, s1, s2);
}

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    scanf ("%d %d", &N, &T);
    for (int i = 1; i <= N; ++i)
        scanf ("%d", V + i);
    buildtree (1, 1, N);
    for (int x, y; T; --T) {
        scanf ("%d %d", &x, &y);
        sum = 0, sol = -0x3f3f3f3f;
        query (1, 1, N, x, y);
        printf ("%lld\n", sol);
    }
}