Choose k Non-Adjacent Servers to Minimize the Largest Chosen Value

A row of `n` servers is numbered `0` to `n - 1` from left to right, and server `i` has an integer value `values[i]`. Choose exactly `k` servers such that no two chosen servers are next to each other in the row. Among all such choices, make the largest value of any chosen server as small as possible, and return that smallest possible largest value. ### Function Signature ```python def min_largest_nonadjacent(values: list[int], k: int) -> int: ``` ### Rules - Servers `i` and `j` are adjacent when `abs(i - j) == 1`. A valid choice is a set of exactly `k` distinct servers that contains no adjacent pair. - The cost of a valid choice is the maximum of `values[i]` over its chosen servers. - Return the minimum cost over all valid choices. The constraints guarantee that at least one valid choice exists. Several choices may reach the minimum; the returned number is the same for all of them. ### Constraints - `1 <= len(values) <= 10^5` - `1 <= values[i] <= 10^9` - `1 <= k <= (len(values) + 1) // 2` ### Examples **Example 1** ```text Input: values = [2, 3, 5, 9], k = 2 Output: 5 ``` The valid choices are servers {0, 2}, {0, 3} and {1, 3}, with costs 5, 9 and 9. **Example 2** ```text Input: values = [5, 1, 1, 5, 2], k = 2 Output: 2 ``` Servers 1 and 2 are the only ones with a value of at most 1, and they are adjacent, so a cost of 1 is impossible. Choosing servers 1 and 4 (values 1 and 2) gives a cost of 2. **Example 3** ```text Input: values = [7, 1, 8, 2, 9], k = 3 Output: 9 ``` The only way to choose three non-adjacent servers out of five is {0, 2, 4}, whose largest value is 9.