Problem Background

Chang'an is wide and the moon is clear, leaving shadows, playing the pipa, the drinkers are half awake.
Ask you what you can't see, the red gauze tent, the green silk tassels, the flying apsaras descending.
The beauty's waist is half inclined, the coral beads are crisp, her slender hand holds the pipa alone, her eyes are still enchanting.
Musk on her lips makes the wine even more intoxicating, the more chaotic the lights, the more beautiful.

——Yin Lin, "Chang'an Fantasy World"

Problem Description

There are $n$ colored lights arranged in a row from left to right, numbered from 1 to $n$, where the brightness of the $i$-th light is $a_i$. For $1 \leq i < n$, we say that the $i$-th light and the $(i + 1)$-th light are adjacent.

We guarantee that the brightness of these $n$ lights is unique.

The harmony level of a group of lights is defined as the difference between the brightest and the dimmest lights in that group.

Fusu wants to select $m$ non-adjacent lights from these $n$ lights to form a group, and she hopes that the harmony level of this group is as small as possible. Please help her find this minimum value.

Formally, you need to select a subsequence of length $m$ from the sequence $a$ of unique elements such that no two elements in the subsequence are adjacent, and the range (difference between the maximum and minimum values) of this subsequence is minimized.

Input Format

The first line contains two integers, representing the number of lights $n$ and the number of lights to be selected $m$.
The second line contains $n$ integers, where the $i$-th integer represents the brightness $a_i$ of the $i$-th light.

Output Format

Output a single integer, which is the answer.

Sample Input and Output

Sample Input #1

5 3
1 2 3 4 5

Sample Output #1

4

Sample Input #2

6 3
1 7 8 3 4 6

Sample Output #2

4

Sample Input #3

See the attached file D3.in

Sample Output #3

See the attached file D3.ans

Notes

Sample 1 Explanation

Only the $1st, 3rd, and 5th$ lights can be selected. Any other selection would result in adjacent lights.

Sample 2 Explanation

The $2nd, 4th, and 6th$ lights can be selected, with brightnesses $7, 3, 6$, and the range is $4$.

Data Constraints

• For $12\%$ of the data, $n \leq 6$.
• For $36\%$ of the data, $n \leq 100$.
• For another $4\%$ of the data, $m = \lceil\frac{n}{2}\rceil$.
• For another $12\%$ of the data, $a_i$ is monotonically increasing.
• For $76\%$ of the data, $n \leq 10^3$.
• For $100\%$ of the data, $1 \leq n \leq 10^5$, $1 \leq m \leq \lceil\frac{n}{2}\rceil$, $1 \leq a_i \leq 10^9$, and $a_i$ are unique.

见题面 Input 部分

见题面 Output 部分