Contest Duration: ~ (local time) (100 minutes) Back to Home
D - Dice in Line /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

N 個のサイコロが左から右に一列に並べてあります。左から i 番目のサイコロは 1 から p_i までの p_i 種類の目がそれぞれ等確率で出ます。

制約

• 1 ≤ K ≤ N ≤ 200000
• 1 ≤ p_i ≤ 1000
• 入力で与えられる値は全て整数

入力

N K
p_1 ... p_N


出力

なお、想定解答との絶対誤差または相対誤差が 10^{-6} 以下であれば正解として扱われる。

入力例 1

5 3
1 2 2 4 5


出力例 1

7.000000000000


入力例 2

4 1
6 6 6 6


出力例 2

3.500000000000


どのサイコロを選んで振っても、出る目の期待値は 3.5 です。

入力例 3

10 4
17 13 13 12 15 20 10 13 17 11


出力例 3

32.000000000000


Score : 400 points

Problem Statement

We have N dice arranged in a line from left to right. The i-th die from the left shows p_i numbers from 1 to p_i with equal probability when thrown.

We will choose K adjacent dice, throw each of them independently, and compute the sum of the numbers shown. Find the maximum possible value of the expected value of this sum.

Constraints

• 1 ≤ K ≤ N ≤ 200000
• 1 ≤ p_i ≤ 1000
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
p_1 ... p_N


Output

Print the maximum possible value of the expected value of the sum of the numbers shown.

Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-6}.

Sample Input 1

5 3
1 2 2 4 5


Sample Output 1

7.000000000000


When we throw the third, fourth, and fifth dice from the left, the expected value of the sum of the numbers shown is 7. This is the maximum value we can achieve.

Sample Input 2

4 1
6 6 6 6


Sample Output 2

3.500000000000


Regardless of which die we choose, the expected value of the number shown is 3.5.

Sample Input 3

10 4
17 13 13 12 15 20 10 13 17 11


Sample Output 3

32.000000000000