D - Dice in Line /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

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

隣接する K 個のサイコロを選んでそれぞれ独立に振ったとき、出る目の合計の期待値の最大値を求めてください。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

N K
p_1 ... p_N

出力

隣接する K 個のサイコロを選んで振ったときに出る目の合計の期待値の最大値を出力せよ。

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


入力例 1

5 3
1 2 2 4 5

出力例 1

7.000000000000

左から 3 番目、4 番目、5 番目のサイコロを振った時、出る目の合計の期待値は 7 となり、これが最大です。


入力例 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