#include <bits/stdc++.h>

using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");

const int NMAX = 100005;
const long long INF = -100000000000;

struct AINT {
    long long val, l, r, s;
}aint[4 * NMAX];

void update(int x, int pos, int node, int le, int ri) {
    if(le == ri)
        aint[node].val = aint[node].l = aint[node].r = aint[node].s = x;
    else {
        int mid = (le + ri) /2;
        if(pos <= mid)
            update(x, pos, node * 2, le, mid);
        else
            update(x, pos, node * 2 + 1, mid + 1, ri);
        aint[node].val = max(aint[node * 2].val, aint[node * 2 + 1].val);
        aint[node].val = max(aint[node].val, aint[node * 2].r + aint[node * 2 + 1].l);
        aint[node].l = aint[node * 2].l;
        aint[node].l = max(aint[node].l, aint[node * 2].s + aint[node * 2 + 1].l);
        aint[node].r = aint[node * 2 + 1].r;
        aint[node].r = max(aint[node].r, aint[node * 2 + 1].s + aint[node * 2].r);
        aint[node].s = aint[node * 2].s + aint[node * 2 + 1].s;
    }
}

long long s, ans;
void query(int from, int to, int node, int le, int ri) {
    if(from <= le && ri <= to) {
        ans = max(ans, max(aint[node].val, aint[node].l + s));
        s = max(s, max(aint[node].s + s, aint[node].r));
    } else {
        int mid = (le + ri) / 2;
        if(from <= mid)
            query(from, to, node * 2, le, mid);
        if(mid < to)
           query(from, to, node * 2 + 1, mid + 1, ri);
    }
}

int main() {

    int n, m;
    in >> n >> m;
    for(int i = 1; i <= n; i ++) {
        int x;
        in >> x;
        update(x, i, 1, 1, n);
    }
    while(m --) {
        int x, y;
        in >> x >> y;
        s = 0;
        ans = INF;
        query(x, y, 1, 1, n);
        out << ans << "\n";
    }
    return 0;
}