Background

The bright moon over Chang'an is clear. Shadows remain, pipa songs go on, and the drinkers are half awake.
You ask, but cannot see clearly. Red gauze curtains, green silk ribbons, and the flying apsaras descend.
A beauty bends her slim waist, her jingling necklaces crisp. With a delicate hand she raises the pipa alone and kneels, her eyes still full of charm.
Musk touches her lips, and the wine becomes more intoxicating. In the drunken lantern light, the colors grow messier yet more beautiful.

— Yin Lin, “Chang'an Fantasy Paintings”

Problem Description

There are $n$ colored lanterns arranged in a row from left to right, numbered from $1$ to $n$. The brightness of lantern $i$ is $a_i$. For $1 \leq i < n$, we say lantern $i$ and lantern $i + 1$ are adjacent.

It is guaranteed that the brightness values of these $n$ lanterns are all distinct.

The harmony of a group of lanterns is defined as the difference between the maximum and minimum brightness among the lanterns in the group.

Fusu wants to choose $m$ non-adjacent lanterns from these $n$ lanterns as a group, and she wants the harmony of this group to be as small as possible. Please help her find this minimum value.

Formally, you need to select a subsequence of length $m$ with pairwise non-adjacent elements from the sequence $a$ (where all elements are distinct), such that the range of the subsequence is minimized.

Input Format

The first line contains two integers, representing the number of lanterns $n$ and the number of lanterns to pick $m$, respectively.
The second line contains $n$ integers. The $i$-th integer represents the brightness $a_i$ of lantern $i$.

Output Format

Output one line with one integer, the answer.

5 3
1 2 3 4 5

4

6 3
1 7 8 3 4 6

4

见附加文件中的 D3.in

见附加文件中的 D3.ans

Hint

Explanation for Sample 1

You can only choose lanterns $1, 3, 5$, because any other selection would cause some lanterns to be adjacent.

Explanation for Sample 2

You can choose lanterns $2, 4, 6$. Their brightness values are $7, 3, 6$, and the range is $4$.

Constraints

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

Translated by ChatGPT 5