Problem

The task is to implement a linear time randomized algorithm for the selection problem.

Given: A positive integer $n \le 10^5$ and an array $A[1..n]$ of integers from $-10^5$ to $10^5$, a positive number $k \le n$.

Return: The $k$-th smallest element of $A$.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

Sample Dataset

11
2 36 5 21 8 13 11 20 5 4 1
8

Sample Output

13