Se citesc un vector cu n numere intregi si un numar natural k (1 <= k <= n). Determinati al k-lea cel mai mic element din vector (elementul de pe pozitia k, daca vectorul ar fi sortat crescator), folosind algoritmul Quickselect: o varianta Divide et Impera a algoritmului Quicksort care, dupa fiecare partitionare, continua recursiv doar in partea care contine pozitia cautata, fara a mai sorta si cealalta parte.
- Date de intrare
- Pe prima linie se citeste numarul natural n. Pe a doua linie se citesc cele n numere intregi ale vectorului, separate prin spatiu. Pe a treia linie se citeste numarul natural k (1 <= k <= n).
- Date de iesire
- Se afiseaza al k-lea cel mai mic element din vector.
- Restrictii
- 1 <= n <= 100000, -10^9 <= a[i] <= 10^9, 1 <= k <= n
Exemple
Exemplul 1
Intrare
5 7 2 9 4 1 1
Iesire
1
Exemplul 2
Intrare
5 7 2 9 4 1 5
Iesire
9