Problem Description

Given a sequence \( a \) of \( n \) integers, find a contiguous subsequence of length at least \( k \) such that the average of all numbers in this subsequence is maximized.

Input Format

The input consists of 2 lines.

The first line contains two integers \( n \) and \( k \).
The second line contains \( n \) integers \( a_1, a_2, \dots, a_n \), representing the sequence \( a \).

Output Format

Output a single line containing a real number, which is the maximum average value of a contiguous subsequence of length at least \( k \).

For each test case, your program will be considered correct if the relative error between your answer and the standard answer is no more than \( 10^{-3} \).

Sample Input and Output

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

Notes

[Data Range]

For 30% of the data, \( n \leq 5000 \).
For all data, \( 1 \leq k \leq n \leq 3 \times 10^5 \), \( 1 \leq a_i \leq 10^6 \).

[Problem Source]

This problem is from COCI 2014-2015 CONTEST 7 T5 PROSJEK, configured with the original data. The full score is 140 points.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分