14579 - Ice Cream Shortage   

Description

In a bustling ice cream parlor, customers line up to order their favorite flavors. The shop owner has a peculiar way of managing the queue. Instead of serving customers in their arrival order, the owner wants to serve them based on their heights, from the shortest to the tallest. However, the shop owner had a bad day, only want to serve the person who would be the $k^{th}$ person in line if everyone was arranged by height.

Given the heights of $N$ customers, help the shop owner find out who would be the $k^{th}$ (0-based) person if they were arranged from shortest to tallest.

Input

Input contains two lines. The first line contains two integers $N$ and $k$, the number of people in the queue and the position the shop owner want to find.

The second line contains $N$ integer, where each integer $h_i$ represent the height of the $i^{th}$ customer.

Contraints

  • $1 \leq N \leq 5 \times 10^6$
  • $0 \leq k < N$
  • $0 \leq h_i \leq 10^9$

Subtask

  1. (Testcases 1-4) $N \leq 3 \times 10^3$
  2. (Testcases 5-6) $N \leq 2 \times 10^5$
  3. (Testcases 7-8) No additional constraints.

Output

Output the height of the $k^{th}$ (0-based) customer when they are arranged from shortest to tallest.

Noted that you should output one single line.

Sample Input  Download

Sample Output  Download

Tags




Discuss