#include <cassert>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <memory>
 
using namespace std;
 
constexpr int64_t inf = 1e18;

class Reader {
public:
    Reader(istream& _in) : in(_in), idx(kBuffSize - 1), buff(new char[kBuffSize]) { Advance(); }
    
    Reader& operator>>(char& ch) {
        ch = Current();
        Advance();
        return *this;
    }
    
    Reader& operator>>(char str[]) {
        while (isspace(Current())) {
            Advance();
        }
        
        int n = 0;
        while (not isspace(Current())) {
            str[n++] = Current();
            Advance();
        }
        str[n] = 0;
        return *this;
    }
    
    Reader& operator>>(string& str) {
        while (isspace(Current())) {
            Advance();
        }
        
        while (not isspace(Current())) {
            str.push_back(Current());
            Advance();
        }
        return *this;
    }
    
    Reader& operator>>(int32_t& value) {
        bool sign = false;
        while (not isdigit(Current())) {
            sign |= Current() == '-';
            Advance();
        }
        
        value = 0;
        while (isdigit(Current())) {
            value = (value << 1) + (value << 3) + (Current() - '0');
            Advance();
        }
        value ^= (value ^ -value) & -sign;
        return *this;
    }
    
    Reader& operator>>(int64_t& value) {
        bool sign = false;
        while (not isdigit(Current())) {
            sign |= Current() == '-';
            Advance();
        }
        
        value = 0;
        while (isdigit(Current())) {
            value = (value << 1) + (value << 3) + (Current() - '0');
            Advance();
        }
        value ^= (value ^ -value) & -sign;
        return *this;
    }
    
    Reader& operator>>(double& value) {
        bool sign = false;
        while (not isdigit(Current())) {
            sign |= Current() == '-';
            Advance();
        }
        
        value = .0;
        while (isdigit(Current())) {
            value = value * 10.0 + (Current() - '0');
            Advance();
        }
        if (Current() == '.') {
            Advance();
            
            double multiplier = 0.1;
            while (isdigit(Current())) {
                value += (Current() - '0') * multiplier;
                multiplier *= 0.1;
                Advance();
            }
        }
        
        if (sign) {
            value = -value;
        }
        return *this;
    }
private:
    static constexpr int kBuffSize = 1 << 12;
    
    char Current() const {
        return buff[idx];
    }
    
    void Advance() {
        if (++idx == kBuffSize) {
            in.read(buff.get(), kBuffSize);
            idx = 0;
        }
    }
    
    istream& in;
    int idx;
    unique_ptr<char[]> buff;
};

class Printer {
public:
    Printer(ostream& _out) : out(_out), idx(0), buff(new char[kBuffSize]), digits(new char[kMaxNumDigits]) { }
    ~Printer() { Flush(); out.flush(); }

    Printer& operator<<(int32_t value) {
        if (value < 0) {
            PutChar('-');
            value = -value;
        }
        int num_digits = 0;
        do {
            const uint32_t aux = ((uint64_t)3435973837 * value) >> 35;
            digits[num_digits++] = value - (aux << 1) - (aux << 3) + '0';
            value = aux;
        } while (value > 0);
        
        while (num_digits--) {
            PutChar(digits[num_digits]);
        }
        return *this;
    }
    
    Printer& operator<<(int64_t value) {
        if (value < 0) {
            PutChar('-');
            value = -value;
        }
        int num_digits = 0;
        do {
            const uint64_t aux = value / 10;
            digits[num_digits++] = value - (aux << 1) - (aux << 3) + '0';
            value = aux;
        } while (value > 0);
        
        while (num_digits--) {
            PutChar(digits[num_digits]);
        }
        return *this;
    }
    
    Printer& operator<<(const char *str) {
        for (int i = 0; str[i]; i += 1) {
            PutChar(str[i]);
        }
        return *this;
    }
    
    Printer& operator<<(const string& str) {
        for (auto&& ch : str) {
            PutChar(ch);
        }
        return *this;
    }
    
    Printer& operator<<(const char& ch) {
        PutChar(ch);
        return *this;
    }
    
    Printer& operator <<(double value) {
        if (value < 0) {
            PutChar('-');
            value = -value;
        }
        
        const int64_t integer_part = static_cast<int64_t>(value);
        *this << integer_part << '.' << static_cast<int64_t>((value - integer_part) * kPrecision + 0.5);
        return *this;
    }
private:
    static constexpr int kBuffSize = 1 << 12;
    static constexpr int kMaxNumDigits = 20;
    static constexpr double kPrecision = 1e9;
    
    void Flush() {
        out.write(buff.get(), idx);    
    }
    
    void PutChar(const char& ch) {
        buff[idx++] = ch;
        if (idx == kBuffSize) {
            Flush();
            idx = 0;
        }
    }
    
    ostream& out;
    int idx;
    unique_ptr<char[]> buff, digits;    
};

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 <<= 1;
        }
         
        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[(i << 1) - tree_size], (i << 1) - tree_size)
                     + NodeValue(leaves[(i<<1|1) - tree_size], (i<<1|1) - tree_size);
        }
        for (int i = (tree_size >> 1) - 1; i > 0; i -= 1) {
            nodes[i] = nodes[i << 1] + nodes[(i << 1) | 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 >> 1); i -= 1) {
            idx_left[i] = (i << 1) - tree_size;
            idx_right[i] = ((i << 1) | 1) - tree_size;
        }
        for (int i = (tree_size >> 1) - 1; i > 0; i -= 1) {
            idx_left[i] = idx_left[i << 1];
            idx_right[i] = idx_right[(i << 1) | 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 ((node << 1) < tree_size) {
            delta[node << 1] += delta[node];
            delta[node<<1|1] += delta[node];
        } else {
            delta[node].AddToLeaf(leaves[(node << 1) - tree_size], (node << 1) - tree_size);
            delta[node].AddToLeaf(leaves[(node<<1|1) - tree_size], (node<<1|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);
    
    Reader r(cin);
    Printer p(cout);
    int n, q; r >> n >> q;
    vector<LeafValue> v(n);
    for (auto& el : v) {
        r >> el.x;
    }
     
    LazySegmentTree tree(v);
    while (q--> 0) {
        int left, right; r >> left >> right; left -= 1; right -= 1;
        p << tree.GetRange(left, right + 1).mx_sum << '\n';
    }
    return 0;
}