Problem Description

Given a sequence $a$ of $n$ integers, find a contiguous subsequence of length at least $k$ such that the average value of all numbers in this subsequence is as large as possible.

Input Format

The input has $2$ lines.

The first line contains two integers $n, k$.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$, representing all elements of the sequence $a$.

Output Format

Output one line containing a real number, representing the maximum average value among all contiguous subsequences with length at least $k$.

For each test point, your program will pass if the relative error between your output and the standard answer does not exceed $10^{-3}$.

4 1
1 2 3 4

4.000000

4 2
2 4 3 4

3.666666

6 3
7 1 2 1 3 6

3.333333

Hint

Constraints

For $30\%$ of the testdata, $n \leqslant 5000$.
For all testdata, $1 \leqslant k \leqslant n \leqslant 3 \times 10^5$, and $1 \leqslant a_i \leqslant 10^6$.

Source

This problem comes from COCI 2014-2015 CONTEST 7 T5 PROSJEK. With the original testdata configuration, the full score is $140$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5