A

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>

template<class T>
class vector {
public:
    explicit vector() : buffer(nullptr), size(0) {};
    explicit vector(int size);
    explicit vector(int size, T value);
    vector(const vector& other);
    vector(vector&& other);
    vector& operator=(const vector& other);
    vector& operator=(vector&& other);
    ~vector();

    T& operator[](int index) const { return buffer[index]; };

    void resize(int new_size);
    int get_size() const { return size; };
private:
    T* buffer;
    int size;
};

template<class T>
vector<T>::vector(int size) : size(size) {
    buffer = new T[size];
}

template<class T>
vector<T>::vector(int size, T value) : size(size) {
    buffer = new T[size];
    for (int i = 0; i < size; ++i)
        buffer[i] = value;
}

template<class T>
vector<T>::vector(const vector& other) : size(other.size) {
    delete[] buffer;
    buffer = new T[size];
    for (int i = 0; i < size; ++i) {
        buffer[i] = other.buffer[i];
    }
}

template<class T>
vector<T>::vector(vector&& other) : size(0), buffer(nullptr) {
    std::swap(buffer, other.buffer);
    std::swap(size, other.size);
}

template<class T>
vector<T>& vector<T>::operator=(const vector& other) {
    size = other.size;
    delete[] buffer;
    buffer = new T[size];
    for (int i = 0; i < size; ++i) {
        buffer[i] = other.buffer[i];
    }
    return *this;
}

template<class T>
vector<T>& vector<T>::operator=(vector&& other) {
    std::swap(buffer, other.buffer);
    std::swap(size, other.size);
    return *this;
}

template<class T>
vector<T>::~vector()
{
    delete[] buffer;
}

template<class T>
void vector<T>::resize(int new_size) {
    T* new_buffer = new T[new_size];
    for (int i = 0; i < size; ++i) {
        new_buffer[i] = buffer[i];
    }
    size = new_size;
    delete[] buffer;
    buffer = new_buffer;
}

struct node {
    int max_pref;
    int max_suf;
    int sum;
    int max_sum;
    node(int m_p, int m_sf, int s, int m_s) : max_pref(m_p), max_suf(m_sf), sum(s), max_sum(m_s) {}
    node(int v) : max_pref(v), max_suf(v), sum(v), max_sum(v) {}
    node() : max_pref(INT_MIN), max_suf(INT_MIN), sum(0), max_sum(INT_MIN) {}
};

class SegmentTree {
public:
    explicit SegmentTree(const vector<int>& arr);
    node FindMaxSubsegment(int l, int r, int v, int aim_l, int aim_r);
private:
    vector<node> segment_tree;
    node make_node(const node& l, const node& r);
    int size;
};

node SegmentTree::make_node(const node& l, const node& r) {
    node new_node;
    new_node.max_pref = std::max(l.max_pref, l.sum + r.max_pref);
    new_node.max_suf = std::max(r.max_suf, r.sum + l.max_suf);
    new_node.sum = l.sum + r.sum;
    new_node.max_sum = std::max(std::max(l.max_sum, r.max_sum), l.max_suf + r.max_pref);
    return new_node;
}

SegmentTree::SegmentTree(const vector<int>& arr) : size(arr.get_size()) {
    int n = std::pow(2, std::ceil(std::log2(size)));
    segment_tree = vector<node>(n * 2 - 1, node());
    for (int i = n - 1; i < n + size - 1; ++i)
        segment_tree[i] = node(arr[i - n + 1]);
    for (int i = n - 2; i >= 0; --i)
        segment_tree[i] = make_node(segment_tree[2 * i + 1], segment_tree[2 * i + 2]);
}

node SegmentTree::FindMaxSubsegment(int v, int l, int r, int aim_l, int aim_r) {
    if (aim_l == l && aim_r == r)
        return segment_tree[v];
    int mid = (aim_l + aim_r) / 2;
    if (l > mid)
        return FindMaxSubsegment(2 * v + 2, l, r, mid + 1, aim_r);
    if (r <= mid)
        return FindMaxSubsegment(2 * v + 1, l, r, aim_l, mid);
    return make_node(
        FindMaxSubsegment(2 * v + 1, l, mid, aim_l, mid),
        FindMaxSubsegment(2 * v + 2, mid + 1, r, mid + 1, aim_r)
    );
}

int main() {
    int n, sum_m = 0;
    vector<int> ans(0);
    while (std::cin >> n) {
        int m;
        std::cin >> m;
        vector<int> arr(n);
        for (int i = 0; i < n; ++i) {
            int a;
            std::cin >> a;
            arr[i] = a;
        }
        ans.resize(sum_m + m);
        SegmentTree tree(arr);
        for (int i = sum_m; i < sum_m + m; ++i) {
            int a, b;
            std::cin >> a >> b;
            node nd = tree.FindMaxSubsegment(0, a - 1, b - 1, 0, std::pow(2, std::ceil(std::log2(n))) - 1);
            ans[i] = nd.max_sum;
        }
        sum_m += m;
    }
    for (int i = 0; i < sum_m; ++i) {
        std::cout << ans[i] << std::endl;
    }
    return 0;
}