Maximum Height Difference of Selected Trees

You are given N trees with heights and a number K. Your task is to select K trees (if K equals 1, then only one tree is selected) such that the difference between the highest and the lowest heights among the selected trees is maximized. When K is at least 2, the answer is simply the difference between the maximum and minimum tree heights.

Note: Even though K is provided, the maximum possible difference is achieved by selecting the trees with the lowest and highest heights. The result should be given in LaTeX format when mentioning any formulas. For example, the maximum difference can be expressed as \(a_{max} - a_{min}\) where \(a_{max}\) is the maximum height and \(a_{min}\) is the minimum height.

Example: For input N = 7, K = 3 and tree heights [3, 1, 4, 1, 5, 9, 2], the output is 8, since \(9 - 1 = 8\).

inputFormat

The input is given via stdin as follows:

• The first line contains two integers \(N\) and \(K\), where \(N\) is the number of trees and \(K\) is the number of trees to select.
• The second line contains \(N\) space-separated integers, representing the heights of the trees.

outputFormat

Output a single integer to stdout which is the maximum difference between the highest and lowest heights among the selected trees. If K equals 1 (i.e. only one tree is selected), output 0.

7 3
3 1 4 1 5 9 2

8