H. Weather Forecast
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Radewoosh is a meteorologist. Thanks to his research station, he has learned the predicted temperature for the next $$$n$$$ days. The temperature for each day, expressed in Bytenheit degrees, is always a positive integer.

Radewoosh now needs to present the weather forecast on television. To make people happy, tired of the cool climate, he decided to create the impression that it will be quite warm. He has decided to divide the next $$$n$$$ days into $$$k$$$ non-empty intervals so that each day belongs to exactly one interval. Then, in the weather forecast, Radewoosh will only provide $$$k$$$ numbers - the arithmetic averages of the temperatures from the days belonging to the respective intervals.

Radewoosh knows that viewers watching the forecast are very afraid of low temperatures. Therefore, he would like to make a division that maximizes the average temperature in the coldest of the periods he provides (we call a period of days the coldest if none of the remaining periods has a strictly lower average temperature). Help him make such a division!

Input

The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq n$$$) representing the number of days for which Radewoosh has the temperature forecast and the number of periods into which he wants to divide it.

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 1000$$$) representing the temperature on consecutive days, expressed in Bytenheit degrees.

Output

The output should contain a single real number, representing the maximum average temperature in the coldest of the periods. The answer will be accepted if its absolute error does not exceed $$$10^{-4}$$$.

Example
Input
7 3
1 3 1 2 2 2 1
Output
1.666666666667
Note

The days can be divided into periods as follows: $$$[1, 3, 1], [2], [2, 2, 1]$$$. The average temperature in the consecutive intervals will be $$$\frac{5}{3}$$$, $$$2$$$, and $$$\frac{5}{3}$$$, respectively, resulting in a minimum temperature of $$$\frac{5}{3}$$$. This division maximizes the minimum average temperature in a single period.