//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <memory>

using namespace std;

constexpr int64_t inf = 1e18;

struct LeafValue {
    int x; 
    LeafValue(const int _x = 0) : x(_x) { }
};

struct NodeValue {
    int64_t mx_sum, mx_prefix, mx_suffix, sum;
    NodeValue() : mx_sum(-inf), mx_prefix(-inf), mx_suffix(-inf), sum(0) { }
    NodeValue(const LeafValue& value, const int pos) : mx_sum(value.x), mx_prefix(value.x), mx_suffix(value.x), sum(value.x) {
    } 
    
    NodeValue& operator +=(const NodeValue& rhs) {
        mx_sum = max({mx_sum, mx_suffix + rhs.mx_prefix, rhs.mx_sum});
        mx_prefix = max(mx_prefix, sum + rhs.mx_prefix);
        mx_suffix = max(mx_suffix + rhs.sum, rhs.mx_suffix);
        mx_sum = max({mx_sum, mx_prefix, mx_suffix});
        sum += rhs.sum;
        return *this;
    }
    NodeValue operator +(const NodeValue& rhs) const {
        return NodeValue(*this) += rhs;
    }
};

struct LazyValue {
    int delta;
    LazyValue() : delta(0) { }
    LazyValue& operator +=(const LazyValue& rhs) {
        delta += rhs.delta;
        return *this;
    } 
    
    void AddToLeaf(LeafValue& value, int pos) const {
        //value.x += delta;
    }
    
    void AddToNode(NodeValue& value, int left, int right) const {
        //value.mx += delta;
    }
};

class LazySegmentTree {
public:
    LazySegmentTree(int n, const LeafValue& v = LeafValue()) { Init(vector<LeafValue>(n, v)); }
    LazySegmentTree(const vector<LeafValue>& v) { Init(v); }
    
    LeafValue Get(int pos) {
        Propagate(FindIdx(pos, pos + 1));
        return leaves[pos];
    }
    
    NodeValue GetRangeCommutative(int left, int right) {
        Propagate(FindIdx(left, right));
        
        NodeValue answer = NodeValue();
        left += tree_size; right += tree_size;
        while (left < right) {
            if (left & 1) {
                answer += FindNodeValue(left++);
            }
            if (right & 1) {
                answer += FindNodeValue(--right);
            }
            left >>= 1; right >>= 1;
        }
        return answer;
    }
    
    NodeValue GetRange(int left, int right) {
        Propagate(FindIdx(left, right));
        
        NodeValue answer = NodeValue();
        while (left > 0 and left + lsb(left) <= right) {
            answer += FindNodeValue((tree_size + left) / lsb(left));
            left += lsb(left);
        }
        
        int num_idx = 0;
        while (right > left) {
            idx[num_idx++] = (tree_size + right) / lsb(right) - 1;
            right -= lsb(right);
        }
        while (num_idx--) {
            answer += FindNodeValue(idx[num_idx]);
        }
        return answer;
    }
    
    void Set(int pos, const LeafValue& value) {
        const int n = FindIdx(pos, pos + 1);
        Propagate(n);
        leaves[pos] = value;
        Merge(n);
    }
    
    void AddRange(int left, int right, const LazyValue& add) {
        if (left >= right) {
            return;
        }
        
        const int n = FindIdx(left, right);
        Propagate(n);
        left += tree_size; right += tree_size;
        if (left & 1) {
            add.AddToLeaf(leaves[left - tree_size], left - tree_size);
            left += 1;
        }
        if (right & 1) {
            right -= 1;
            add.AddToLeaf(leaves[right - tree_size], right - tree_size);
        }
        
        left >>= 1; right >>= 1;
        while (left < right) {
            if (left & 1) {
                delta[left++] += add;
            }
            if (right & 1) {
                delta[--right] += add;
            }
            left >>= 1; right >>= 1;
        }
        Merge(n);
    }
private:
    static inline int lsb(int value) {
        return value & -value;
    }
    
    void Init(const vector<LeafValue>& v) {
        int n = static_cast<int>(v.size());
        tree_size = 1;
        while (tree_size < n) {
            tree_size *= 2;
        }
        
        leaves = v;
        leaves.resize(tree_size);
        nodes.resize(tree_size);
        for (int i = tree_size - 1; i >= (tree_size / 2); i -= 1) {
            nodes[i] = NodeValue(leaves[2 * i - tree_size], 2 * i - tree_size)
                            + NodeValue(leaves[2 * i + 1 - tree_size], 2 * i + 1 - tree_size);
        }
        for (int i = (tree_size / 2) - 1; i > 0; i -= 1) {
            nodes[i] = nodes[2 * i] + nodes[2 * i + 1];
        }
        delta.assign(tree_size, LazyValue());
        
        idx_left.resize(tree_size);
        idx_right.resize(tree_size);
        for (int i = tree_size - 1; i >= (tree_size / 2); i -= 1) {
            idx_left[i] = 2 * i - tree_size;
            idx_right[i] = 2 * i + 1 - tree_size;
        }
        for (int i = (tree_size / 2) - 1; i > 0; i -= 1) {
            idx_left[i] = idx_left[2 * i];
            idx_right[i] = idx_right[2 * i + 1];
        }
        idx = unique_ptr<int[]>(new int[128]);
    }
    
    NodeValue FindNodeValue(int node) {
        PropagateAt(node);
        return node < tree_size ? nodes[node] : 
                NodeValue(leaves[node - tree_size], node - tree_size);
    }
    
    int FindIdx(int left, int right) {
        if (left >= right) {
            return 0;
        }
        
        int num_idx = 0;
        left = (left + tree_size) >> 1;
        right = (right + tree_size - 1) >> 1;
        while (left != right) {
            idx[num_idx + 0] = left;
            idx[num_idx + 1] = right;
            num_idx += 2;
            left >>= 1; right >>= 1;
        }
        while (left > 0) {
            idx[num_idx++] = left;
            left >>= 1;
        }
        return num_idx;
    } 
    
    void Propagate(int num_idx) {
        while (num_idx--) {
            PropagateAt(idx[num_idx]);
        }
    }
    
    void PropagateAt(int node) {
        if (node >= tree_size) {
            return;
        }
        
        delta[node].AddToNode(nodes[node], idx_left[node], idx_right[node]);
        if (2 * node < tree_size) {
            delta[2 * node + 0] += delta[node];
            delta[2 * node + 1] += delta[node];
        } else {
            delta[node].AddToLeaf(leaves[2 * node - tree_size], 2 * node - tree_size);
            delta[node].AddToLeaf(leaves[2 * node + 1 - tree_size], 2 * node + 1 - tree_size);
        }
        delta[node] = LazyValue();
    }
    
    void Merge(int num_idx) {
        for (int i = 0; i < num_idx; i += 1) {
            MergeAt(idx[i]);
        }    
    }
    
    void MergeAt(int node) {
        if (node < tree_size) {
            nodes[node] = FindNodeValue(node << 1) + FindNodeValue((node << 1) | 1);
        }
    }
    
    vector<LeafValue> leaves;
    vector<NodeValue> nodes;
    vector<LazyValue> delta;
    vector<int> idx_left, idx_right;
    unique_ptr<int[]> idx;
    int tree_size;
};

int main() {
    #ifdef INFOARENA
    ifstream cin("sequencequery.in");
    ofstream cout("sequencequery.out");
    #endif
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int n, q; cin >> n >> q;
    vector<LeafValue> v(n);
    for (auto& el : v) {
        cin >> el.x;
    }
    
    LazySegmentTree tree(v);
    while (q--> 0) {
        int left, right; cin >> left >> right; left -= 1; right -= 1;
        cout << tree.GetRange(left, right + 1).mx_sum << '\n';
    }
    return 0;
}