#include <cstdio>

inline long long max(long long a, long long b) {
    if(a > b) {
        return a;
    } else {
        return b;
    }
}

void* start;

class aint {
public:
    //aint* st;
    //aint* dr;
    long long sol, suma, pref, suf;

    aint() {
        this->sol = 0;
        this->suma = 0;
        this->pref = 0;
        this->suf = 0;
    }

    aint* st() {
        aint* AInt = (aint*)start;
        int i = this - AInt;
        return &AInt[2 * i];
    }

    aint* dr() {
        aint* AInt = (aint*)start;
        int i = this - AInt;
        return &AInt[2 * i + 1];
    }

    aint(aint* st, aint* dr) {
        this->sol = max(st->sol, max(dr->sol, st->suf + dr->pref));
        this->suma = st->suma + dr->suma;
        this->pref = max(st->pref, st->suma + dr->pref);
        this->suf = max(dr->suf, dr->suma + st->suf);
    }

    void update(int St, int Dr, int poz, int val) {
        if(St == Dr) {
            sol = val;
            suma = val;
            if(val > 0) {
                pref = val;
                suf = val;
            } else {
                pref = val;
                suf = val;
            }
        } else {
            if(poz <= (St + Dr) / 2) {
                st()->update(St, (St + Dr) / 2, poz, val);
            } else {
                dr()->update((St + Dr) / 2 + 1, Dr, poz, val);
            }
            sol = max(st()->sol, max(dr()->sol, st()->suf + dr()->pref));
            suma = st()->suma + dr()->suma;
            pref = max(st()->pref, st()->suma + dr()->pref);
            suf = max(dr()->suf, dr()->suma + st()->suf);
        }
    }

    aint* query(int qSt, int qDr, int St, int Dr) {
        //printf("Q: %d %d %d %d\n", qSt, qDr, St, Dr);
        if(qSt <= St && Dr <= qDr) {
            return new aint(*this);
        }
        if(qDr <= (St + Dr) / 2) {
            return this->st()->query(qSt, qDr, St, (St + Dr) / 2);
        } else if((St + Dr) / 2 + 1 <= qSt) {
            return this->dr()->query(qSt, qDr, (St + Dr) / 2 + 1, Dr);
        } else {
            aint* st = this->st()->query(qSt, qDr, St, (St + Dr) / 2);
            aint* dr = this->dr()->query(qSt, qDr, (St + Dr) / 2 + 1, Dr);
            aint* nod = new aint(st, dr);
            delete st;
            delete dr;
            return nod;
        }
    }
};

long long query(int qSt, int qDr, int N, aint* radacina) {
    aint* tmp = radacina->query(qSt, qDr, 1, N);
    long long sol = tmp->sol;
    delete tmp;
    return sol;
}

aint AInt[1 << 18];

int main(void) {
    FILE* f = fopen("sequencequery.in", "r");
    FILE* h = fopen("sequencequery.out", "w");
    int N, M;
    fscanf(f, "%d%d", &N, &M);
    aint* radacina = &AInt[1];
    start = AInt;
    for(int i = 1; i <= N; ++i) {
        int x;
        fscanf(f, "%d", &x);
        radacina->update(1, N, i, x);
        //fprintf(h, "%d\n", query(i, i, N, radacina));
    }
    for( int i = 1; i <= M; ++i) {
        int x, y;
        fscanf(f, "%d%d", &x, &y);
        fprintf(h, "%lld\n", query(x, y, N, radacina));
    }
    return 0;
}