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

#define x1 "sequencequery.in"
#define x2 "sequencequery.out"

ifstream in(x1);
ofstream out(x2);

#define MAXN 100000 * 2


long long v[MAXN], n;

struct seq {
    long long sum, max_sum, lmax_sum, rmax_sum;
} aint[MAXN];

seq add(seq l, seq r) {
    seq ans;
    ans.sum = l.sum + r.sum;

    ans.lmax_sum = max(l.lmax_sum, l.sum + r.lmax_sum);
    ans.rmax_sum = max(r.rmax_sum, r.sum + l.rmax_sum);

    ans.max_sum = max(l.rmax_sum + r.lmax_sum, max(l.max_sum, r.max_sum));
    return ans;
}

void build(int l, int r, int node) {
    if (l == r) {
        aint[node].sum = aint[node].max_sum = aint[node].lmax_sum = aint[node].rmax_sum = v[l];
        return;
    }

    int mid, lChild, rChild;

    mid = (l + r) / 2;
    lChild = node + 1;
    rChild = node + 2 * (mid - l + 1);

    build(l, mid, lChild);
    build(mid + 1, r, rChild);

    aint[node] = add(aint[lChild], aint[rChild]);
}

seq ssm(int l, int r, int a, int b, int node) {
    if(l >= a && r <= b)
        return aint[node];

    int mid, lChild, rChild;

    mid = (l + r) / 2;
    lChild = node + 1;
    rChild = node + 2 * (mid - l + 1);

    if(b <= mid)
        return ssm(l, mid, a, b, lChild);

    if(a > mid)
        return ssm(mid + 1, r, a, b, rChild);

    return add(ssm(l, mid, a, mid, lChild), ssm(mid + 1, r, mid + 1, b, rChild));
}


int main() {
    int cer, a, b, i, q;

    in >> n >> q;

    for(i = 0; i < n; i++)
        in >> v[i];

    build(0, n, 0);

    while(q--) {
        in >> a >> b;
        out << ssm(0, n, a - 1 , b - 1, 0).max_sum << '\n';

    }
    return 0;
}