Minimize Highest Remaining Tree

You are given N trees with their heights provided in an array \(arr\). When you cut a tree, its height immediately becomes \(1\). You are required to cut exactly K trees. Your goal is to choose which trees to cut so that the height of the tallest remaining tree is minimized.

Formally, you need to find the minimum value \(X\) such that after cutting exactly \(K\) trees, every tree that is not cut has a height \(\le X\). Note that if you cut a tree, its new height is \(1\). If \(K = N\), then all trees will be cut and the answer will be \(1\).

Example: For \(N = 5\), \(arr = [3, 1, 4, 2, 5]\), and \(K = 2\), a possible optimal strategy is to cut the trees with heights \(4\) and \(5\). The remaining tree heights become \([3, 1, 2]\) and the highest remaining tree is \(3\). Hence, the answer is \(3\).

inputFormat

The input consists of three lines:

1. The first line contains a single integer \(N\) representing the total number of trees.
2. The second line contains \(N\) space-separated positive integers indicating the heights of the trees.
3. The third line contains a single integer \(K\), the number of trees to cut.

outputFormat

Output a single integer representing the minimized height of the highest remaining tree after cutting exactly \(K\) trees.

## sample

5
3 1 4 2 5
2

3

</p>