That's it. Sgt. Laugh has had enough. He is determined to end the evil military reign of General Cry. But Laugh isn't stupid. He knows, he needs a team to break through the walls of Cry.
Platoon "BattleCry'' has $n$ soldiers. Laugh will choose $k$ of these soldiers. The platoon is lined up. Height of the soldier $i$ is represented by $h_i$. The sergeant wiil choose the soldiers in a way so that their heights form a strictly increasing sequence, i.e. if he chooses soldiers with indices $i_1, ~i_2, .. ~i_{k-1}, ~i_k$ where $i_1 < i_2 < i_3 .. < i_k$ , condition $h_{i_1} < h_{i_2} < h_{i_3} .. < h_{i_k}$ must hold. Also since the sergeant is a little bit picky, the height difference between the tallest and shortest soldier must be minimum possible.
Help Laugh choose the squad.
Input
First line of input contains two integers $n, ~k$ .
The following line contains $n$ integers representing the heights of the soldiers $h_i$.
Constraints
$1 \leq n \leq 2 \times 10^5$.$1 \leq k \leq \min(n, ~30)$.$1 \leq h_i \leq 10^9$.
Output
If no such squad could be formed, print $-1$ on a line.
Otherwise, output the minimum possible difference between the tallest and shortest soldier in the chosen squad.
Samples
| Input | Output |
|---|---|
5 3 12 14 11 12 15 | 3 |
| Input | Output |
|---|---|
5 3 5 4 1 4 4 | -1 |
