#include <fstream>
#include <cstring>
#include <vector>
typedef long long ll;

class InParser {
    private:
        std::vector<char> str;
        int ptr;
        std::ifstream fin;
    
    private:
        char getChar() {
            if (ptr == (int)str.size()) {
                fin.read(str.data(), (int)str.size());
                ptr = 0;
            }

            return str[ptr++];
        }

        template<class T>
        T getInt() {
            char chr;
            do {
                chr = getChar();
            } while (!isdigit(chr) && (chr != '-'));

            int sgn = +1;
            if (chr == '-') {
                sgn = -1;
                chr = getChar();
            }

            T num = 0;
            while (isdigit(chr)) {
                num = num * 10 + (chr - '0');
                chr = getChar();
            }

            return sgn * num;
        }
    
    public:
        InParser(const char *name) : str((int)1e5), ptr((int)str.size()), fin(name) { }
        ~InParser() { fin.close(); }

        template<class T>
        friend InParser &operator >> (InParser &in, T &num) {
            num = in.getInt<T>();
            return in;
        }
};

class OutParser {
    private:
        std::vector<char> str;
        int ptr;
        std::ofstream fout;
    
    private:
        void putChar(char chr) {
            if (ptr == (int)str.size()) {
                fout.write(str.data(), (int)str.size());
                ptr = 0;
            }

            str[ptr++] = chr;
        }

        template<class T>
        void putInt(T num) {
            if (num < 0) {
                putChar('-');
                num *= -1;
            }

            if (num > 9)
                putInt(num / 10);
            putChar(num % 10 + '0');
        }
    
    public:
        OutParser(const char *name) : str((int)1e5), ptr(0), fout(name) { }
        ~OutParser() { fout.write(str.data(), ptr); fout.close(); }

        template<class T>
        friend OutParser &operator << (OutParser &out, const T num) {
            out.putInt(num);
            return out;
        }

        friend OutParser &operator << (OutParser &out, const char chr) {
            out.putChar(chr);
            return out;
        }

        friend OutParser &operator << (OutParser &out, const char *str) {
            for (int i = 0; str[i]; i++)
                out.putChar(str[i]);
            return out;
        }
};

const int INF = 2e9;

typedef struct {
    ll sum;
    ll pref;
    ll suff;
    ll smax;
} data;

class SegmentTree {
    private:
        std::vector<data> tree;
        int n;
    
    public:
        SegmentTree(int _n) {
            this->n = _n;
            tree.resize(n << 2);
        }
        ~SegmentTree() { }

        data init(int delta) {
            data res;
            res.sum = delta;
            res.suff = res.pref = res.smax = delta;
            return res;
        }

        data combine(data a, data b) {
            data res;
            res.sum = a.sum + b.sum;
            res.pref = std::max(a.pref, a.sum + b.pref);
            res.suff = std::max(b.suff, b.sum + a.suff);
            res.smax = std::max(std::max(a.smax, b.smax), a.suff + b.pref);
            return res;
        }

        void build(int node, int l, int r, std::vector<int> &nums) {
            if (l == r) {
                tree[node] = init(nums[l]);
                return;
            }

            int m = (l + r) >> 1;

            build(node << 1, l, m, nums);
            build(node << 1 | 1, m + 1, r, nums);

            tree[node] = combine(tree[node << 1], tree[node << 1 | 1]);
        }

        data query(int node, int l, int r, int x, int y) {
            if (x <= l && r <= y)
                return tree[node];
            if (x > r || y < l)
                return {-INF, -INF, -INF, -INF};
            
            int m = (l + r) >> 1;

            return combine(query(node << 1, l, m, x, y),
                           query(node << 1 | 1, m + 1, r, x, y));
        }
};

int n, q;
std::vector<int> nums;

int main() {
    InParser cin("sequencequery.in");
    OutParser cout("sequencequery.out");

    cin >> n >> q;
    nums.resize(n + 1);

    for (int i = 1; i <= n; i++)
        cin >> nums[i];

    SegmentTree sgt(n);
    sgt.build(1, 1, n, nums);
    
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << sgt.query(1, 1, n, l, r).smax << '\n';
    }
    return 0;
}