Floor Cube Root, Negatives Included

Given an integer n (possibly negative), return the largest integer k such that k ** 3 <= n.

Note that for negative n the floor rounds away from zero: for n = -9 the answer is -3, because (-2) ** 3 = -8 is greater than -9.

Examples

Input:  n = 27
Output: 3

Input:  n = 26
Output: 2

Input:  n = -9
Output: -3

Constraints

• -10**18 <= n <= 10**18
• O(log |n|) time; use exact integer arithmetic (no ** (1/3)).

Goals

• Search a range that spans negative and positive values
• Apply the floor definition correctly to negative inputs