Background

The wind chimes hanging under the eaves sound pleasant as they sway.
Longing is like the endless plum rain, leaving my mood a muddy mess.
The scattered stars across the sky sparkle with the fate we share.
When maple leaves lightly fall into the heart of the lake, the nearby view is calm and peaceful.

— Yin Lin & Han Yu, Bitter Bamboo Grove

Problem Description

There are $n$ wind chimes hanging under the eaves, and each wind chime can produce a sound of a certain pitch. Number the wind chimes from left to right from $1$ to $n$. The pitch of the $i$-th wind chime is $a_i$.

To express his longing, Fusu decides to take $m$ out of the $n$ wind chimes and give them to a friend far away.

Please find the minimum integer $\varepsilon$ such that there exists a way to choose $m$ wind chimes from the $n$ wind chimes. Let the pitches of the selected wind chimes be $b_1, b_2, \dots, b_m$. They must satisfy that for any $1 \leq i, j \leq m$, we have $|b_i - b_j| \leq \varepsilon$.

Input Format

The first line contains two integers, representing the number of wind chimes $n$ and the number of wind chimes to select $m$.
The second line contains $n$ integers, representing the pitch of each wind chime. The $i$-th integer is $a_i$.

Output Format

Output one integer on a single line, representing the minimum $\varepsilon$.

5 3
1 2 3 4 5

2

6 4
1 7 8 3 4 6

4

Hint

Explanation for Sample 2

One possible plan is to choose the $2, 4, 5, 6$-th wind chimes, with pitches $7, 3, 4, 6$ in order. Then for any $1 \leq i, j \leq 4$, we have $|b_i - b_j| \leq 4$.

Another plan is to choose the $2, 3, 5, 6$-th wind chimes. The computed $\varepsilon$ is also $4$.

Constraints

• For $10\%$ of the testdata, $m = 2$.
• For another $10\%$ of the testdata, $m = n$.
• For $40\%$ of the testdata, $n \leq 5$.
• For $60\%$ of the testdata, it is guaranteed that for all $2 \leq i \leq n$, $a_{i - 1} \leq a_i$, i.e., $a_i$ is non-decreasing.
• For $80\%$ of the testdata, $n \leq 10^3$.
• For $100\%$ of the testdata, $2 \leq m \leq n \leq 10^5$, and $1 \leq a_i \leq 10^9$.

Notes

This problem provides three additional sample files. See ring.zip in the attachments.

Translated by ChatGPT 5