#include <bits/stdc++.h>

using namespace std;
const int NMAX = 1e5 + 1;

#define int long long int

struct nod {
    int sum;
    int pref_sum;
    int suff_sum;
    int scmax;
};

nod tree[4*NMAX];

int n, m, v[NMAX];

nod mergee(nod stanga, nod dreapta) {
    nod ans;
    ans.sum = stanga.sum + dreapta.sum;
    ans.pref_sum = max(stanga.pref_sum, stanga.sum + dreapta.pref_sum);
    ans.suff_sum = max(dreapta.suff_sum, dreapta.sum + stanga.suff_sum);
    ans.scmax = max({stanga.scmax, dreapta.scmax, stanga.suff_sum + dreapta.pref_sum});
    return ans;
}

void build(int node, int st, int dr) {
    if (st == dr)
        tree[node].sum = tree[node].pref_sum = tree[node].scmax = tree[node].suff_sum = v[st];
    else {
        int mij = (st + dr) / 2;
        build(node*2, st, mij);
        build(node*2+1, mij+1, dr);
        tree[node].sum = tree[node*2].sum + tree[node*2+1].sum;
        tree[node].pref_sum = max(tree[node*2].pref_sum, tree[node*2].sum + tree[node*2+1].pref_sum);
        tree[node].suff_sum = max(tree[node*2+1].suff_sum, tree[node*2+1].sum + tree[node*2].suff_sum);
        tree[node].scmax = max({tree[node*2].scmax, tree[node*2+1].scmax, tree[node*2].suff_sum + tree[node*2+1].pref_sum});
    }
}

void update(int node, int st, int dr, int poz, int val) {
    if (st == dr)
        tree[node].sum = tree[node].pref_sum = tree[node].scmax = tree[node].suff_sum = val, v[st] = val;
    else {
        int mij = (st + dr) / 2;
        if (poz <= mij)
            update(node*2, st, mij, poz, val);
        if (poz > mij)
            update(node*2+1, mij+1, dr, poz, val);
        tree[node].sum = tree[node*2].sum + tree[node*2+1].sum;
        tree[node].pref_sum = max(tree[node*2].pref_sum, tree[node*2].sum + tree[node*2+1].pref_sum);
        tree[node].suff_sum = max(tree[node*2+1].suff_sum, tree[node*2+1].sum + tree[node*2].suff_sum);
        tree[node].scmax = max({tree[node*2].scmax, tree[node*2+1].scmax, tree[node*2].suff_sum + tree[node*2+1].pref_sum});
    }
}

nod query(int node, int st, int dr, int left, int right) {
    if (left <= st && dr <= right)
        return tree[node];
    else {
        int mij = (st + dr) / 2;
        if (left > mij)
            return query(node*2+1, mij+1, dr, left, right);
        else if (right <= mij)
            return query(node*2, st, mij, left, right);
        else {
            nod stanga = query(node*2, st, mij, left, right);
            nod dreapta = query(node*2+1, mij+1, dr, left, right);
            return mergee(stanga, dreapta);
        }
    }
}

signed main()
{
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        int st, dr;
        cin >> st >> dr;
        cout << query(1, 1, n, st, dr).scmax << '\n';
    }
    return 0;
}