Compute for . Optimal splits are monotonic. Start with range . Compute (midpoint). Find by trying all valid splits. Say . Recurse on with constraint . Recurse on with constraint .
Each level does work total (all ranges at that level partition the search space). levels gives .