#include <iostream>
#include <fstream>
using namespace std;

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

const int MAXN = 1e5;

struct nodAINT {
    int total;
    int secventa;
    int st, dr;
} aint[4*MAXN];

int n, nrq, a, b, x;
long long maxSecv, secv_ramas;

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

void update(int a, int b, int nod, int poz, int val) {
    if (a == b) {
        aint[nod] = {val, val, val, val};
        return;
    }

    int mid = (a + b) / 2;
    if (poz <= mid)
        update(a, mid, 2*nod, poz, val);
    else
        update(mid + 1, b, 2*nod + 1, poz, val);

    aint[nod].secventa = max(max( aint[2*nod].secventa, aint[2*nod + 1].secventa ), aint[2*nod].dr + aint[2*nod + 1].st);

    aint[nod].st = max(aint[2*nod].st, aint[2*nod + 1].st + aint[2*nod].total);
    aint[nod].dr = max(aint[2*nod + 1].dr, aint[2*nod].dr + aint[2*nod + 1].total);

    aint[nod].total = aint[2*nod].total + aint[2*nod + 1].total;
}

void query(int a, int b, int nod, int st, int dr) {
    if (st <= a && b <= dr) {
        maxSecv = maxl(aint[nod].secventa, aint[nod].st + secv_ramas);
        secv_ramas = max(secv_ramas + aint[nod].total, aint[nod].dr);

        if (secv_ramas < 0)
            secv_ramas = 0;

        return;
    }

    int mid = (a + b) / 2;

    if (st <= mid)
        query(a, mid, 2*nod, st, dr);
    if (mid < dr)
        query(mid + 1, b, 2*nod + 1, st, dr);
}

int main() {
    in >> n >> nrq;
    for (int i = 1; i <= n; i++) {
        in >> x;
        update(1, n, 1, i, x);
    }

    for (int i = 1; i <= nrq; i++) {
        in >> a >> b;

        maxSecv = -1e6;
        secv_ramas = 0;

        query(1, n, 1, a, b);

        out << maxSecv << '\n';
    }

    return 0;
}