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

#define inf (1LL<<60)
#define L (nod << 1)
#define R L | 1
struct lel{
    ll st, dr, val, s;
} a[400010];
ll n, m, val, idx, l, r, ans, aux;

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);
}

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;
    if (l <= mid && r <= mid) return query(L, st, mid);
    if (r > mid && l > mid) return query(R, mid + 1, dr);
    if (l <= mid && r > mid){
        lel left = query(L, st, mid);
        lel right = query(R, mid + 1, dr);
        lel aux;
        aux.s = left.s + right.s;
        aux.val = max(max(left.val, right.val), left.dr + right.st);
        aux.st = max(left.st, left.s + right.st);
        aux.dr = max(right.dr, right.s + left.dr);
        return aux;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    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;
}