Find all non-extendable ranges in an array of real values with a non-positive sum

Question

I have a long array of size $n>10^6$, call it $X$. I would like to find all ranges $[a, b)$ satisfying the following conditions

1. $\sum_{i=a}^{b-1}X[i] \leq 0$,
2. $b-a \geq K$,
3. $\sum_{i=a-1}^{b-1} X[i] > 0$,
4. $\sum_{i=a}^{b} X[i] > 0$.

I also would like to note that $X[i]$s can only take $m$ distinct values, typically $m<10$. A quadratic time algorithm is trivial. I'm wondering if I can do any better than that.

• greybeard: Can you use prefix sums to advantage?
• greybeard: "[time] any better than [quadratic]" you may have to do an output sensitive analysis ($t = f(n) + c_2(|output|)$): there may be $O(n^2)$ such ranges/pairs.
• cebir latis: Oh, got it. I think I'll have to come up with a more constrained version of 3 and 4. Thanks!
• D.W.: Is $K$ small compared to $n$ or large? Would you be satisfied with a sub-quadratic algorithm that finds a single such interval? Do you already know of such an algorithm?
• cebir latis: I came up with an $O(n \log n)$ for the relaxed version I mentioned in my above comment. I'll add as an answer once I am confident.