#include <fstream>
#include <climits>

#define MAXN 100005

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

long long secv[MAXN * 4], L[MAXN * 4], R[MAXN * 4], ait[MAXN * 4];
long long in[MAXN], sol, ssm;

inline void Build(int poz, int st, int dr) {
    int mij = (st + dr) / 2;

    if (st == dr) {
        secv[poz] = L[poz] = R[poz] = ait[poz] = in[st];
    }
    else {
        Build(poz * 2, st, mij);
        Build(poz * 2 + 1, mij + 1, dr);

        ait[poz] = ait[poz * 2] + ait[poz * 2 + 1];
        secv[poz] = max(secv[poz * 2], max(secv[poz * 2 + 1], R[poz * 2] + L[poz * 2 + 1]));
        L[poz] = max(L[poz * 2], ait[poz * 2] + L[poz * 2 + 1]);
        R[poz] = max(R[poz * 2 + 1], R[poz * 2] + ait[poz * 2 + 1]);
    }
}

inline void Query(int poz, int st, int dr, int ls, int ld) {
    int mij = (st + dr) / 2;

    if (ls > dr || ld < st)
        return;
    if (ssm < 0)
        ssm = 0;
    if (ls <= st && dr <= ld) {
        sol = max(sol, max(secv[poz], ssm + L[poz]));
        ssm = max(ssm + ait[poz], R[poz]);
    }
    else {
        Query(poz * 2, st, mij, ls, ld);
        Query(poz * 2 + 1, mij + 1, dr, ls, ld);
    }
}

inline void Read() {
    int N, m, a, b;

    fin >> N >> m;

    for (int i = 1; i <= N; i++)
        fin >> in[i];

    Build(1, 1, N);

    for (int i = 1; i <= m; i++) {
        fin >> a >> b;

        sol = ssm = INT_MIN;
        Query(1, 1, N, a, b);

        fout << sol << "\n";
    }
}

int main () {
    Read();

    fin.close(); fout.close(); return 0;
}