Minimum Harmony Range

There are n colored lamps arranged in a row and numbered from 1 to n from left to right. The brightness of the i-th lamp is given by \(a_i\), and all brightness values are distinct. For \(1 \le i < n\), lamp \(i\) and lamp \(i+1\) are considered adjacent.

The harmony of a set of lamps is defined as the difference between the maximum and minimum brightness values in the set. Fusu wants to select m lamps such that no two selected lamps are adjacent, and she wishes the harmony of the selected set to be as small as possible. Formally, given a sequence of distinct integers \(a_1, a_2, \dots, a_n\), choose a subsequence of length m with no two consecutive indices such that the range (i.e. \(\max - \min\)) is minimized. Your task is to compute this minimum possible difference.

inputFormat

The first line contains two integers n and m (number of lamps and number of lamps to choose, respectively). The second line contains n space-separated integers \(a_1, a_2, \dots, a_n\), representing the brightness of each lamp.

outputFormat

Output a single integer, the minimum possible harmony (difference between maximum and minimum brightness) among any valid selection of m non-adjacent lamps.

sample

5 3
4 1 10 8 2

8