D. Odd-Even Subsequencetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputAshish 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.InputThe 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.OutputOutput a single integer  — the minimum cost of a subsequence of size k.ExamplesInput
4 2
1 2 3 4
Output
1Input
4 3
1 2 3 4
Output
2Input
5 3
5 3 4 2 6
Output
2Input
6 4
5 3 50 2 4 5
Output
3NoteIn 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.
4 2
1 2 3 4

1
['binary search', 'dp', 'dsu', 'greedy', 'implementation', '*2000']