#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const long long INF = 1000000000000000000;
const int mod = 1e9 + 7;
const char out[2][4]{ "NO", "YES" };
#define all(a) a.begin(), a.end()
using ll = long long;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

#define variableName(var) #var
#define __debug(var) cout << #var << " = " << var << '\n'
inline int rint(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }

const int nmax = 1e5;
int n, q;
int a[nmax + 5]{ 0 };

struct Node {
    ll prefix;
    ll suffix;
    ll kadane;
    ll sum;
    Node() {
        prefix = suffix = kadane = sum = 0;
    }
    Node(int value) {
        prefix = suffix = kadane = sum = value;
    }
} t[nmax * 4 + 5];

Node merge(const Node& left, const Node& right) {
    Node result;
    result.prefix = max(left.prefix, left.sum + right.prefix);
    result.suffix = max(right.suffix, left.suffix + right.sum);
    result.kadane = max({ left.kadane, right.kadane, left.suffix + right.prefix });
    result.sum = left.sum + right.sum;
    return result;
}

void build(int node, int l, int r) {
    if (l == r) {
        t[node] = Node(a[l]);
        return;
    }
    int mid = (l + r) / 2;
    build(node << 1, l, mid);
    build(node << 1 | 1, mid + 1, r);
    t[node] = merge(t[node << 1], t[node << 1 | 1]);
}

Node query(int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return t[node];
    }
    int mid = (l + r) / 2;
    if (ql <= mid) {
        if (mid < qr) {
            return merge(query(node << 1, l, mid, ql, qr),
                query(node << 1 | 1, mid + 1, r, ql, qr));
        }
        else {
            return query(node << 1, l, mid, ql, qr);
        }
    }
    else {
        return query(node << 1 | 1, mid + 1, r, ql, qr);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    fin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        fin >> a[i];
    }
    build(1, 1, n);
    while (q--) {
        int x, y;
        fin >> x >> y;
        fout << query(1, 1, n, x, y).kadane << nl;
    }
}