#include <fstream>
#include <algorithm>
#include <iostream>

using namespace std;

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

const int MAX_N = 100000;

struct Node {
    long long left;
    long long right;
    long long best;
    long long sum;
};
Node T[2*MAX_N + 1];

Node join(Node u, Node v) {
    Node w;
    if(u.sum + v.left >= u.left)
        w.left = u.sum + v.left;
    else w.left = u.left;
    if(v.sum + u.right >= v.right)
        w.right = v.sum + u.right;
    else w.right = v.right;
    w.sum = u.sum + v.sum;
    w.best = max(max(u.best, v.best), u.right + v.left);
    return w;
}


void update(int x, int l, int r, int p, int v) {
    if(r - l == 1) {
        T[x] = {v, v, v, v};
        return;
    }
    if(p < (r+l)/2)
        update(2*x, l, (r+l)/2, p, v);
    else
        update(2*x+1, (r+l)/2, r, p, v);
    T[x] = join(T[2*x], T[2*x+1]);
}

Node query(int x, int l, int r, int i, int j) {
    if(i <= l && r <= j)
        return T[x];
    else if(j <= (r+l)/2)
        return query(2*x, l, (r+l)/2, i, j);
    else if(i >= (r+l)/2)
        return query(2*x+1, (r+l)/2, r, i, j);
    else
        return join(query(2*x, l, (r+l)/2, i, j), query(2*x+1, (r+l)/2, r, i, j));
}

void print(int x, int offset) {
    if(x > 30) return;
    for(int i = 1; i <= offset; i++)
        out << ' ';
    out << T[x].left << " " << T[x].right << " " << T[x].best << " " << T[x].sum << '\n';
    print(2*x, offset+4);
    print(2*x+1, offset+4);
}

int main() {
    int n, m, i, x, l, r;

    in >> n >> m;
    for(i = 1; i <= n; i++) {
        in >> x;
        update(1, 1, n+1, i, x);
    }

    for(i = 1; i <= m; i++) {
        in >> l >> r;
        out << query(1, 1, n+1, l, r+1).best << '\n';
    }

    //out << '\n';
    //print(1, 0);



    return 0;
}