# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Sgt. Laugh

By reborn · 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.

## 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


• DP

### Statistics

39% Solution Ratio

tmwilliamlin168Earliest, Jan '20

tmwilliamlin168Fastest, 0.7s 