Cubes arrive one at a time, in the given order, and you must place each one as it arrives. A cube can go on top of an existing tower only if the cube currently on top of that tower is strictly larger. Otherwise (or if you prefer) it starts a new tower.
Write min_towers(cubes: list[int]) -> int: the fewest towers you can end up with.
Examples:
min_towers([3, 8, 2, 1, 5]) == 2(towers3,2,1and8,5)min_towers([1, 2, 3]) == 3min_towers([4, 4]) == 2(equal sizes can't stack)
Constraints: 1 <= len(cubes) <= 200_000, sizes between 1 and 10^9.
Some tests end up with many towers at once, so trying every tower for each cube is too slow; aim for O(n log n).
Show hint
putting each cube on the tower whose top is the smallest value still larger than the cube is always safe. The tops stay sorted, so that tower can be found by binary search.