#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

const ll INF = 1e10;

ll max(ll a, ll b, ll c) {
    return max(a, max(b, c));
}
ll max(ll a, ll b, ll c, ll d) {
    return max(max(a, b, c), d);
}

struct Node {
    ll le, ri, sum, mx;
};
Node nothing = {-INF, -INF, -INF, -INF};

struct SegTree {
    vector < Node > T;

    Node MergeNodes(const Node &a, const Node &b) {
        Node aux = nothing;
        aux.sum = a.sum + b.sum;
        aux.mx = max(a.mx, b.mx, a.ri + b.le);
        aux.le = max(a.le, a.sum + b.le);
        aux.ri = max(b.ri, b.sum + a.ri);
        aux.mx = max(aux.sum, aux.le, aux.ri, aux.mx);

        return aux;
    }
    void Build(int node, int lo, int hi, const vector < int > &V) {
        if(lo == hi) {
            T[node].le = T[node].ri = T[node].sum = T[node].mx = V[lo - 1];
        } else {
            int mid = (lo + hi) / 2;

            Build(node * 2, lo, mid, V);
            Build(node * 2 + 1, mid + 1, hi, V);
           T[node] = MergeNodes(T[node * 2], T[node * 2 + 1]);
        }
    }

    Node Query(int node, int lo, int hi, int b, int e) {
        if(lo > e || hi < b || lo > hi) return nothing;
        if(lo >= b && hi <= e) return T[node];

        int mid = (lo + hi) / 2;
        return MergeNodes(Query(node * 2, lo, mid, b, e), Query(node * 2 + 1, mid + 1, hi, b, e));

    }

    SegTree(const vector < int > &V) : T(4 * (int)V.size()) {
        Build(1, 1, (int)V.size(), V);
    }
};

int main() {
    int n, q;
    fin >> n >> q;

    vector < int > v(n);
    for(auto &it: v) 
        fin >> it;

    SegTree tree(v);

    while(q--) {
        int a, b;
        fin >> a >> b;

        Node ans = tree.Query(1, 1, n, a, b);

        fout << ans.mx << "\n";
    }
    return 0;
}