Sgt. Laugh

reborn Mirror of NSTU ICE Fest R...
Limits 2.5s, 256 MB

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

InputOutput
5 3
12 14 11 12 15
3
InputOutput
5 3
5 4 1 4 4
-1

Submit

Login to submit.

Statistics

42% Solution Ratio
tmwilliamlin168Earliest, Jan '20
tawsifrahmanFastest, 0.6s
Mr_BangladeshLightest, 12 MB
Deshi_TouristShortest, 950B
Toph uses cookies. By continuing you agree to our Cookie Policy.