Divide and Conquer: kth Smallest Number

You are given n numbers and an integer k. Your task is to find the kth smallest element among these numbers, where the smallest element is considered the 0th smallest. The number n is an odd integer satisfying $1 \le n < 5000000$, and each number $a_i$ satisfies $1 \le a_i < 10^9$. Note that this problem emphasizes the use of a divide and conquer strategy rather than built-in library functions such as nth_element.

Hint: Consider implementing the Quickselect algorithm by partitioning the array around a pivot.

inputFormat

The input consists of two lines:

• The first line contains two integers n and k ($1 \le n < 5000000$, n is odd, and $0 \le k < n$).
• The second line contains n space-separated integers: $a_0, a_1, \dots, a_{n-1}$ ($1 \le a_i < 10^9$).

outputFormat

Output a single integer: the kth smallest element in the array.

Remember: The smallest element is the 0th smallest.

sample

5 2
3 1 9 4 6

4