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

#define reset -(1<<29)
#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);
}

void 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){
        ans = max(ans, max(aux + a[nod].st, a[nod].val));
        aux = max(0LL, max(a[nod].dr, aux + a[nod].s));
        return;
    }
    int mid = (st + dr) >> 1;
    if (l <= mid) query(L, st, mid);
    if (r > mid) query(R, mid + 1, dr);
}

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;
        ans = -(1<<30);
        aux = 0;
        query(1, 1, n);
        cout << ans << "\n";
    }
    return 0;
}