Expected Difference of Random Subarray Extremes

In this problem, you are given an array of n positive integers \(a_1, a_2, \dots, a_n\). Two players independently choose a contiguous subarray of length \(k\) uniformly at random among the \(n-k+1\) possible subarrays. Bear A records the maximum value \(P\) in his subarray and Bear B records the minimum value \(Q\) in his subarray. The task is to compute the expected value of \(P - Q\).

The expected difference is given by:

[ E(P-Q) = \frac{1}{n-k+1} \sum_{i=1}^{n-k+1} \Big( \max(a_i, a_{i+1}, \dots, a_{i+k-1}) - \min(a_i, a_{i+1}, \dots, a_{i+k-1}) \Big) ]

Calculate and print this expected value. The answer should be output with at least 6 decimal places.

inputFormat

The first line of input contains two integers \(n\) and \(k\) (with \(1 \le k \le n\)). The second line contains \(n\) positive integers \(a_1, a_2, \dots, a_n\) separated by spaces.

outputFormat

Output a single number, the expected value of \(P - Q\) for the randomly chosen subarrays, printed to at least 6 decimal places.

sample

5 3
1 2 3 4 5

2.000000