P9474 [yLOI2022] Chang'an Fantasy Paintings

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

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.

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 one line with one integer, the answer.

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