Remember the Garden Walls problem?
Ali had to increase the height of the garden walls so the children couldn't jump over them. But unfortunately, those children are so smart that they keep finding ways of getting into the garden even after he increased the wall heights.
And since they keep coming for the fruit trees inside, Ali was fed up with them that he decided to cut some of those trees down. Because Ali loves fruits and can't live without them, he figured he'd keep some trees for himself; so he decided to cut down $k$ trees only.
In order to do that, Ali wants to buy an axe to chop the trees down, so he went to the store and found that there are many different axes with different durabilities, and that an axe's price is higher when its durability is higher.
Ali only wants to pay as much as he needs to, so he has asked you - as you are a good friend of him - to figure out for him what's the minimum durability of an axe $d$ he has to buy in order to fulfill his task.
There are $n$ trees in Ali's garden, each tree has a toughness $t_i$, and Ali is able to chop down a tree if and only if the current durability of the axe is greater than or equal to the tree's toughness ($d$ $\ge$ $t_i$). Every time you chop down a tree, the durability of the axe is decreased by one.
Given all that information, find the minimum durability of an axe $d$ Ali needs such that he can cut at least $k$ trees from his garden.
The first line contains two integers $n$ and $k$ $(1 \le k \le n \le 10^5)$ -- the number of the trees in the garden and the number of the trees he wants to cut respectively.
The second line contains $n$ integers $t_1, t_2, \ldots, t_n$ $(1 \le t_i \le 10^9)$ -- the trees' toughness.
Print one integer $d$ representing the minimum durability needed to fulfill the task at hand.
| Input | Output |
|---|---|
4 2 1 2 3 4 Copy
|
2 Copy
|
4 2 4 2 2 5 Copy
|
3 Copy
|
Since Ali doesn't care about which trees to cut, it's obvious that it's always better for us to cut trees with toughness as low as possible. So we can only consider the smallest $k$ values from the list of tree toughness and ignore the others.
It can also be proven that when presented with multiple trees to cut, it's always better to start cutting the tree with the maximum toughness first, as there's a better chance of cutting all trees that way, since the durability of the axe only goes down afterwards.
So we can now consider all trees to be cut, knowing for each tree its toughness and the order in which it'll be cut, we find the minimum durability of an axe needed to be able to cut that specific tree in that order (regardless of the other trees).
Namely, if we take the minimum $k$ toughness values and sort them in an ascending manner; for a specific tree $i$ $(1 \le i \le k)$, having toughness $t_i$, we know that the durability of the axe should be high enough that after cutting all the trees after $i$ in our ordering, the axe should have durability of at least $t_i$.
In other words, we know that $d \ge t_i + n - i$, and since the axe needs to satisfy that for all $(1 \le i \le k)$, our answer (the needed axe durability) would be equal to the maximum of these calculated values at least.