Quick Select

easy

1. You are given an array(arr) of integers.
2. You have to find the k-th smallest element in the given array using the quick-select algorithm.

Input Format

An Integer n arr1 arr2.. n integers An integer k

Output Format

Check the sample output and question video.

Constraints

1 &lt;= N &lt;= 100000
-10^9 &lt;= arr[i] &lt;= 10^9
1 &lt;= k &lt;= N

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

Output

pivot -> 3
Swapping -2 and 7
Swapping 1 and 7
Swapping 3 and 4
pivot index -> 2
3

Quick Sort

Count Sort