Problem E
Dream Luck

Thumbnail of "How lucky is too lucky?" on TockTick, video by Sit-down Codes

The next big craze on the video sharing site TockTick is the “Mega Luck Challenge”. The videos are daily gaining views in the millions. This week the most popular videos were about a soda machine accidently giving two drinks instead of one, finding a 1000 SEK bill on the ground or narrowly dodging a falling tree branch. Your plan is to take part in this Mega Luck Challenge. So you have recorded yourself rolling a $(10^9 + 1)$-sided die $N$-times in a row to show off your mega luck. Unfortunately it turned out that you were not really lucky, and the result from the recording was not impressive to say the least.

Your back up plan is to instead upload a shorter clip from the long recording where you happen to be lucky. You define the Dream Luck of a clip as the frequency of the most frequent outcome. For example if you are able to find a clip where two thirds of the rolls result in a $6$, then that would have a dream luck of $2/3$.

You’ve decided that you want to upload a clip containing at least $K$ rolls with the maximum possible dream luck. Given a list of outcomes of the $N$ rolls as well as the integer $K$, find the interval of length $\geq K$ that maximizes the dream luck!

Input

The first line of input contains the integers $N$ and $K$ ($1 \leq K \leq N \leq 3\cdot 10^5$).

The second line contains $N$ integers $a_i$ ($0 \leq a_i \leq 10^9$).

Output

Print one real number, the maximum dream luck among all intervals of length $\geq K$. Your answer will be correct if it has an absolute or relative error of at most $10^{-6}$.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

3 2
1 2 1

0.666666666667

7 3
0 2 2 2 3 2 4

1

7 5
1 2 3 4 5 6 6

0.4