#include <iostream> #include<string> #include <list> #include <vector> #include <map> #include <set> #include <unordered_map> #include <unordered_set> #include <algorithm> #include <iomanip> using namespace std; // 插入排序 template<class randomaccessiterator, class T> void _unguarded_insert_aux(randomaccessiterator last, T value) { randomaccessiterator next = last - 1; while (*next >value) { *last = *next; last = next; --next; } *last = value; } template<class randomaccessiterator> void _insert_aux(randomaccessiterator first, randomaccessiterator last) { typedef typename std::iterator_traits<randomaccessiterator>::value_type T; T value = *last; if (*first > value) { std::copy_backward(first, last, last + 1); *first = value; } else _unguarded_insert_aux(last, value); } template<class randomaccessiterator> void _insert_sort(randomaccessiterator first, randomaccessiterator last) { randomaccessiterator tmp = first + 1; while (tmp != last) { _insert_aux(first, tmp); ++tmp; } } //求 数组首、中、尾元素的中位数，防止分割恶化 template<class T> inline const T& _median(const T&a, const T&b, const T&c) { if (a < b) { if (b < c) return b; else if (a<c) return c; else return a; } else { if (c > a) return a; else if (c>b)return c; else return b; } } //做分割处理 template<class randomaccessiterator, class T> randomaccessiterator t_pivot_partition(randomaccessiterator first, randomaccessiterator last, T pivot) { while (true) { while (*first < pivot) ++first; --last; while (*last > pivot) --last; if (!(first < last)) return first; std::swap(*first, *last); ++first; } } //求区间第k小的元素 template <class RandomAccessIterator> void my_nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last) { while (last - first >= 3) { RandomAccessIterator tmp = t_pivot_partition(first, last, _median(*first, *(last - 1), *(first + (last - first) / 2))); if (tmp <= nth) first = tmp; else last = tmp; } _insert_sort(first, last); } //包装函数 int KthArray(vector<int>& nums,int k) { my_nth_element(nums.begin(),nums.begin()+k,nums.end()); return *(nums.begin() + k); } int main() { int n; vector<int> vec; while (cin>>n) { vec.push_back(n); } int k = vec[vec.size() - 1]; vec.pop_back(); cout << KthArray(vec, vec.size()-k)<< endl; return 0; }