Write length_of_lis(nums: list[int]) -> int: the length of the longest strictly increasing subsequence of nums (elements kept in order, not necessarily adjacent).
Examples:
length_of_lis([4, 1, 5, 2, 6, 3, 7]) == 4(e.g.1, 2, 3, 7)length_of_lis([5, 5, 5]) == 1(equal values don't count as increasing)length_of_lis([9, 7, 4]) == 1
Constraints: 1 <= len(nums) <= 100_000, values fit in 32-bit ints (may be negative).
The O(n²) DP is the usual first answer, but the tests use 100k elements, so aim for O(n log n).
Show hint
for each length k, keep the smallest value that an increasing subsequence of length k can end with. That list stays sorted, so each new number can find its place in it by binary search.