Odd-Even Subsequence
Contest: Codeforces Round 651 (Div. 2)
Difficulty rating: 2000
Tags: binary search, dp, dsu, greedy, implementation

Ashish has an array $$$a$$$ of size $$$n$$$.

A subsequence of $$$a$$$ is defined as a sequence that can be obtained from $$$a$$$ by deleting some elements (possibly none), without changing the order of the remaining elements.

Consider a subsequence $$$s$$$ of $$$a$$$. He defines the cost of $$$s$$$ as the minimum between:

- The maximum among all elements at odd indices of $$$s$$$.
- The maximum among all elements at even indices of $$$s$$$.

Note that the index of an element is its index in $$$s$$$, rather than its index in $$$a$$$. The positions are numbered from $$$1$$$. So, the cost of $$$s$$$ is equal to $$$min(max(s_1, s_3, s_5, \ldots), max(s_2, s_4, s_6, \ldots))$$$.

For example, the cost of $$$\{7, 5, 6\}$$$ is $$$min( max(7, 6), max(5) ) = min(7, 5) = 5$$$.

Help him find the minimum cost of a subsequence of size $$$k$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq k \leq n \leq 2 \cdot 10^5$$$)  — the size of the array $$$a$$$ and the size of the subsequence.

The next line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)  — the elements of the array $$$a$$$.

Output format:
Output a single integer  — the minimum cost of a subsequence of size $$$k$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test, consider the subsequence $$$s$$$ = $$$\{1, 3\}$$$. Here the cost is equal to $$$min(max(1), max(3)) = 1$$$.

In the second test, consider the subsequence $$$s$$$ = $$$\{1, 2, 4\}$$$. Here the cost is equal to $$$min(max(1, 4), max(2)) = 2$$$.

In the fourth test, consider the subsequence $$$s$$$ = $$$\{3, 50, 2, 4\}$$$. Here the cost is equal to $$$min(max(3, 2), max(50, 4)) = 3$$$.

Example input:
4 2
1 2 3 4

Example output:
1

Example input:
4 3
1 2 3 4

Example output:
2

Editorial:
Key Idea:
Binary search over the answer and check if given $$$x$$$, it is possible to form a subsequence of length at least $$$k$$$ such that either all elements at odd indices or even indices are $$$\le x$$$.
Solution:
Let us binary search over the answer and fix if the answer comes from elements at odd or even indices in the subsequence. Suppose we want to find if there exists a subsequence of length at least $$$k$$$ such that the elements at odd indices are $$$\le x$$$. We will construct the subsequence greedily.
Let's iterate on the array from left to right. Suppose we are at index $$$i$$$ in the array and the current length of the subsequence formed is $$$l$$$. If $$$l$$$ is odd, the next added element would be at an even index. In this case, we do not care about what this element is as we only want elements at odd indices to be $$$\le x$$$. So, in this case, we add $$$a_i$$$ to the subsequence. If $$$l$$$ is even, then the next added element would be at an odd index, so, it must be $$$\le x$$$. If $$$a_i \le x$$$, we can add $$$a_i$$$ to the subsequence, otherwise we do not add $$$a_i$$$ to the subsequence and continue to the next element in $$$a$$$.
Note that we can do a similar greedy construction for elements at even indices. If the length of the subsequence formed is $$$\ge k$$$ (either by construction from odd indices or even indices), then the answer can be equal to $$$x$$$ and we can reduce the upper bound of the binary search otherwise we increase the lower bound.
Time Complexity - $$$O(n \cdot log_2 (A_i))$$$ or $$$O(n \cdot log_2 (n))$$$