#include <bits/stdc++.h>
using namespace std;

#define reset -(1<<29)
#define L (nod << 1)
#define R L | 1
struct lel{
    int st, dr, val, s;
} a[400010];
int n, m, val, idx, l, r;

void update(int nod, int st, int dr){
    if (st == dr){
        a[nod] = {val, val, val, val};
        return;
    }
    int mid = (st + dr) >> 1;
    if (idx <= mid) update(L, st, mid);
    else update(R, mid + 1, dr);
    a[nod].s = a[L].s + a[R].s;
    a[nod].val = max(max(a[L].val, a[R].val), a[L].dr + a[R].st);
    a[nod].st = max(a[L].st, a[L].s + a[R].st);
    a[nod].dr = max(a[R].dr, a[R].s + a[L].dr);
    //if (a[L].st == a[L].s) a[nod].st = a[L].st + a[R].dr;
    //else a[nod].st = a[L].st;
    //if (a[R].dr == a[R].s) a[nod].dr = a[R].dr + a[L].dr;
    //else a[nod].dr = a[R].dr;
    //a[nod].val = max(max(a[L].val, a[R].val), max(a[nod].st, a[nod].dr));
}

lel query(int nod, int st, int dr){
    cout << st << " " << dr << ":" << a[nod].val << " " << a[nod].st << " " << a[nod].dr << "\n";
    if (st >= l && dr <= r) return a[nod];
    int mid = (st + dr) >> 1;
    lel left = {reset, reset, reset, reset}, right = {reset, reset, reset, reset};
    if (l <= mid) left = query(L, st, mid);
    if (r > mid) right = query(R, mid + 1, dr);
    left.val = max(max(left.val, right.val), left.dr + right.st);
    left.st = max(left.st, left.s + right.st);
    right.dr = max(right.dr, right.s + left.dr);
    left.s += right.s;
    return left;
}

int main(){
    ifstream cin ("sequencequery.in");
    ofstream cout ("sequencequery.out");
    cin >> n >> m;
    for (int i=1; i<=n; i++) cin >> val, idx = i, update(1, 1, n);
    for (int i=1; i<=m; i++) cin >> l >> r, cout << query(1, 1, n).val << "\n";
    return 0;
}