#include <fstream>

#define inf 6000000000LL
#define MAXN 100005

using namespace std;

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

struct str{
    long long ssm, st, dr, sum;
};

str INF = {-inf, -inf, -inf, -inf};

long long v[MAXN];
str ait[MAXN * 4];

inline void Build(int poz, int st, int dr) {
    if (st == dr) {
        ait[poz].ssm = ait[poz].st = ait[poz].dr = ait[poz].sum = v[st];
        return;
    }
    int mij = (st + dr) / 2;

    Build(poz * 2, st, mij);
    Build(poz * 2 + 1, mij + 1, dr);
    ait[poz].ssm = max(ait[poz * 2].ssm, max(ait[poz * 2 + 1].ssm, ait[poz * 2].dr + ait[poz * 2 + 1].st));
    ait[poz].st = max(ait[poz * 2].st, ait[poz * 2].sum + ait[poz * 2 + 1].st); ait[poz].dr = max(ait[poz * 2 + 1].dr, ait[poz * 2].dr + ait[poz * 2 + 1].sum);
    ait[poz].sum = ait[poz * 2].sum + ait[poz * 2 + 1].sum;
}

inline int IsEgal(str a1, str a2) {
    if (a1.ssm == a2.ssm && a1.st == a2.st && a1.dr == a2.dr && a1.sum == a2.sum)
        return 1;
    return 0;
}

str Query(int poz, int st, int dr, int ls, int ld) {
    if (ls <= st && dr <= ld) {
        return ait[poz];
    }
    if (st > ld || dr < ls) {
        return INF;
    }

    int mij = (st + dr) / 2;

    str aux1 = Query(poz * 2, st, mij, ls, ld);
    str aux2 = Query(poz * 2 + 1, mij + 1, dr, ls, ld);

    if (IsEgal(aux1, INF))
        return aux2;
    else if (IsEgal(aux2, INF))
        return aux1;
    else {
        long long maxi = max(aux1.ssm, max(aux2.ssm, aux1.dr + aux2.st));
        aux1.st = max(aux1.st, aux1.sum + aux2.st); aux2.dr = max(aux2.dr, aux2.sum + aux1.dr);
        return {maxi, aux1.st, aux2.dr};
    }
}

void Read() {
    int N, M; long long x, y; str aux;

    fin >> N >> M;

    for (int i = 1; i <= N; i++) {
        fin >> v[i];
    }

    Build(1, 1, N);

    while (M--) {
        fin >> x >> y;
        aux = Query(1, 1, N, x, y);

        fout << aux.ssm << "\n";
    }
}

int main () {
    Read();

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