Minimized Maximum of Non-Adjacent Picks

You are given an integer array nums and an integer k.

Choose at least k elements of nums such that no two chosen elements are adjacent in the array. The cost of a choice is the maximum value among the chosen elements.

Return the minimum possible cost. The input always admits a valid choice of k non-adjacent elements.

Examples

Example 1

Input: nums = [2, 3, 5, 9], k = 2
Output: 5
Explanation: Choosing indices 0 and 2 (values 2 and 5) gives cost 5. Choosing
2 and 9 gives 9, and 3 and 9 gives 9, so 5 is the best achievable.

Example 2

Input: nums = [2, 7, 9, 3, 1], k = 2
Output: 2
Explanation: Indices 0 and 4 (values 2 and 1) are non-adjacent; the cost is 2.