#include <bits/stdc++.h>
#define int long long

using namespace std;

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

const int INF = 1e16L;

class node {
    public:
        int sum, pref, suf, max_sum;
};

class SegTree {
    public:
        int Size;
        vector<node> tree;

        SegTree(int N) {
            Size = 1;
            while(Size < N)
                Size <<= 1;
            tree.assign(Size << 1 | 1, {0, -INF, -INF, -INF});
        }

        node Merge(const node &A, const node &B) {
            node ans;
            ans.sum = A.sum + B.sum;
            ans.pref = max(A.pref, A.sum + B.pref);
            ans.suf = max(B.suf, A.suf + B.sum);
            ans.max_sum = max({A.max_sum, B.max_sum, A.suf + B.pref, ans.pref, ans.suf, ans.sum, A.pref, A.suf, B.pref, B.suf});
            return ans;
        }

        void build(int x, int lx, int rx) {
            if(lx == rx) {
                fin >> tree[x].sum;
                tree[x].pref = tree[x].suf = tree[x].max_sum = tree[x].sum;
                return;
            }
            int mid = (lx + rx) >> 1;
            build(x << 1, lx, mid);
            build(x << 1 | 1, mid + 1, rx);
            tree[x] = Merge(tree[x << 1], tree[x << 1 | 1]);
        }

        void update(int x, int lx, int rx, int poz, int val) {
            if(lx == rx) {
                tree[x] = {val, val, val, val};
                return;
            }
            int mid = (lx + rx) >> 1;
            if(poz <= mid)
                update(x << 1, lx, mid, poz, val);
            else
                update(x << 1 | 1, mid + 1, rx, poz, val);
            tree[x] = Merge(tree[x << 1], tree[x << 1 | 1]);
        }

        node query(int x, int lx, int rx, int st, int dr) {
            if(st <= lx && rx <= dr)
                return tree[x];
            int mid = (lx + rx) >> 1;
            node ans1{0, -INF, -INF, -INF}, ans2 = ans1;
            if(st <= mid)
                ans1 = query(x << 1, lx, mid, st, dr);
            if(mid < dr)
                ans2 = query(x << 1 | 1, mid + 1, rx, st, dr);
            return Merge(ans1, ans2);
        }
};

int32_t main() {
    int N, Q;
    fin >> N >> Q;
    SegTree tree(N);
    tree.build(1, 1, N);
    while(Q--) {
        int st, dr;
        fin >> st >> dr;
        fout << tree.query(1, 1, N, st, dr).max_sum << '\n';
    }
}