COCI '14 Contest 7 #5 Prosjek

Points: 15 (partial)

Time limit: 0.6s

Memory limit: 64M

Author:

Problem type

You are given an array of $N$ ~N~ integers. Find a consecutive subsequence of numbers of the length at least $K$ ~K~ that has the maximal possible average.

Please note: the average of a subsequence is the sum of all the numbers in the subsequence divided by its length.

Input

The first line of input contains two integers $N$ ~N~ $(1 \le N \le 3\cdot10^5)$ ~(1 \le N \le 3\cdot10^5)~ and $K$ ~K~ $(1 \le K \le N)$ ~(1 \le K \le N)~. The second line of input contains $N$ ~N~ integers $a_i$ ~a_i~ $(1 \le a_i \le 10^6)$ ~(1 \le a_i \le 10^6)~

Output

The first and only line of output must contain the maximal possible average. An absolute deviation of $\pm0.001$ ~\pm0.001~ from the official solution is permitted.

Scoring

In test cases worth 30% of total points, it will hold that $N$ ~N~ is not larger than $5\,000$ ~5\,000~.

Sample Input 1

4 1
1 2 3 4

Sample Output 1

4.000000

Sample Input 2

4 2
2 4 3 4

Sample Output 2

3.666666

Sample Input 3

6 3
7 1 2 1 3 6

Sample Output 3

3.333333

Comments

1

Y commented on Aug. 11, 2019, 10:54 p.m.

Please notice that it is expected to output finite number of digits after the decimal.